ABSTRACT. We study deterministic pushdown automata operating with translucent input letters. These devices can be obtained by equipping classical deterministic pushdown automata with a translucency function which, depending on the current state, establishes the set of invisible input symbols: such symbols are skipped in the current move and dealt with in subsequent sweeps, while the first visible symbol from the current input head position is processed. Translucent deterministic pushdown automata can be returning, meaning that a new input sweep starts from the leftmost input symbol immediately after processing a visible symbol, or not. We show some incomparability results between the acceptance capability of returning and non-returning translucent deterministic pushdown automata and that of non-returning translucent deterministic and nondeterministic finite state automata. Then, we prove the non-closure of families of languages accepted by returning and non-returning translucent deterministic pushdown automata under concatenation, Kleene star, length-preserving and inverse homomorphism, reversal, and intersection with regular languages. In particular, arguments used to prove non-closure under this last language operation, enable us to answer a question on non-returning translucent deterministic finite state automata left open in the literature.

ABSTRACT. Bidirectional deterministic finite automata (biDFA) are a recent innovation with many potential applications. In this paper, we present novel theoretical results for bidirectional automata. We show that there exist regular languages, where minimal biDFA models are exponentially smaller than minimal DFA models. We show this for a language that has a structure common to software logs. This makes biDFA especially interesting when inferring models from such data. However, we also prove that the problem of biDFA minimisation is NP-hard. As our key contribution we provide a Myhill-Nerode style congruence-based characterisation for the languages they can recognise. Since most algorithms for learning DFAs are based on such a congruence, this characterisation is an important building block for obtaining learning algorithms.

ABSTRACT. Register automaton (RA) and register context-free grammar (RCFG) are extensions of finite automaton and context-free grammar by adding the ability of data manipulation in a restricted way. This paper reviews definitions and basic properties of RA and RCFG. As a related topic, logics on data words, namely, linear-time temporal logic (LTL) with freeze quantifier and two-variable first-order logic with data equality are explained. Finally, nominal automaton, which can be regarded as a group-theoretic generalization of RA, is briefly described.

ABSTRACT. We study the termination of sole combinatory calculus, which consists of only one combinator. Specifically, the termination for non-erasing combinators is disproven by finding a desirable tree automaton with a SAT solver as done for term rewriting systems by Endrullis and Zantema. We improved their technique to apply to non-erasing sole combinatory calculus, in which it suffices to search tree automata with a final sink state. Our method succeeds in disproving the termination of 8 combinators, which have been unknown of their termination.

ABSTRACT. Attributed tree transducers (atts) have been equipped with regular look-around (i.e., a preprocessing via an attributed relabeling) in order to obtain a more robust class of translations. Here we give further evidence of this robustness: we show that if the class of translations realized by nondeterministic atts with regular look-around is restricted to partial functions, then we obtain exactly the class of translations realized by deterministic atts with regular look-around.

ABSTRACT. We introduce global one-counter tree automata (GOCTA) which deviate from usual counter tree automata by working on only one counter which is passed to the tree in lexicographical order, rather than duplicating the counter at every branching position. We compare the capabilities GOCTA to that of counter tree automata and obtain that their classes of recognizable tree languages are incomparable. Moreover, we show that the emptiness problem of GOCTA is undecidable while, in stark contrast, their membership problem is in P.

ABSTRACT. We show that the n'th digit of the base-b representation of the golden ratio is a finite-state function of the Zeckendorf representation of b^n, and hence can be computed by a finite automaton. Similar results can be proven for any quadratic irrational. We use a satisfiability (SAT) solver to prove, in some cases, that the automata we construct are minimal.

ABSTRACT. Many natural language processing systems operate over tokenizations of text to address the open-vocabulary problem. In this paper, we give and analyze an algorithm for the efficient construction of deterministic finite automata designed to operate directly on tokenizations produced by the popular byte pair encoding technique. This makes it possible to apply many existing techniques and algorithms to the tokenized case, such as pattern matching, equivalence checking of tokenization dictionaries, and composing tokenized languages in various ways.

ABSTRACT. Patterns are strings with terminals and variables. The language of a pattern is the set of words obtained by substituting all variables with words that contain only terminals. Regular constraints restrict valid substitutions of variables by equipping each variable with a regular language representable by, e.g., finite automata. Pattern languages with regular constraints contain only words in which each variable is substituted according to a set of regular constraints. We consider the membership, inclusion, and equivalence problems for erasing and non-erasing pattern languages with regular constraints. Our main result shows that the erasing equivalence problem—one of the most prominent open problems in the realm of patterns—becomes undecidable if regular constraints are allowed in addition to variable equality.