Abstract. The relationship between automata and logics has been investigated since the 1960s. In particular, it was shown how to determine, given an automaton, whether or not it is definable in first-order logic with label tests and the order relation, and for first-order logic with the successor relation. In recent years, there has been much interest in languages over an infinite alphabet. Kaminski and Francez introduced a class of automata called finite memory automata (FMA), that represent a natural analog of finite state machines. A FMA can use, in addition to its control state, a (bounded) number of registers to store and compare values from the input word. The class of data languages recognized by FMA is incomparable with the class of data languages defined by firstorder formulas with the order relation and an additional binary relation for data equality. We first compare the expressive power of several variants of FMA with several data word logics. Then we consider the corresponding decision problem: given an automaton A and a logic, can the language recognized by A be defined in the logic? We show that it is undecidable for several variants of FMA, and then investigate the issue in detail for deterministic FMA. We show the problem is decidable for first-order logic with local data comparisons -an analog of first-order logic with successor. We also show instances of the problem for richer classes of first-order logic that are decidable. Logics are natural ways of specifying decision problems on discrete structures, while automata represent natural processing models. On finite words from a fixed (finite) alphabet, Büchi [1] showed that monadic second-order logic has the same expressiveness as deterministic finite state automata, while results of Schützenberger and McNaughton and Papert showed that first-order logic with the label and order predicates has the same expressiveness as counter-free automata [2, 3] . The latter theorem gives a decidable characterization of which automata correspond to first-order sentences. Decidable characterizations have also been given for first-order logic with the label and successor predicates [4] . These characterizations have been extended to many other contexts; for example there are characterizations of the tree automata that correspond to sentences in logics on trees [5] . Automata processing finite words over infinite alphabets (so called data words) are attracting significant interest from the database and verification communities, since they can be often used as low-level formalisms for representing and reasoning about data streams, program traces, and serializations of structured documents. Moreover, properties specified using high-level formalisms (for
In REF , they show that definability in first-order logic is undecidable if the input is a nondeterministic register automaton.
Automata vs. logics on data words
In CSL, volume 6247 of LNCS
Computer Science