Partially Ordered Two-way Büchi Automata
arXiv:1006.2719 · doi:10.1007/978-3-642-18098-9_20
Abstract
We introduce partially ordered two-way Büchi automata and characterize their expressive power in terms of fragments of first-order logic FO[<]. Partially ordered two-way Büchi automata are Büchi automata which can change the direction in which the input is processed with the constraint that whenever a state is left, it is never re-entered again. Nondeterministic partially ordered two-way Büchi automata coincide with the first-order fragment Sigma2. Our main contribution is that deterministic partially ordered two-way Büchi automata are expressively complete for the first-order fragment Delta2. As an intermediate step, we show that deterministic partially ordered two-way Büchi automata are effectively closed under Boolean operations. A small model property yields coNP-completeness of the emptiness problem and the inclusion problem for deterministic partially ordered two-way Büchi automata.
The results of this paper were presented at CIAA 2010; University of Stuttgart, Computer Science