Partially ordered two-way Büchi automata

DOI10.1007/978-3-642-18098-9_20MaRDI QIDQ3073637zbMATH OpenOpenAlexFDO

Authors Manfred Kufleitner, Alexander Lauser

Publication date 11 February 2011

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.2719

Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Abstract: We introduce partially ordered two-way B"uchi automata and characterize their expressive power in terms of fragments of first-order logic FO[<]. Partially ordered two-way B"uchi automata are B"uchi 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"uchi automata coincide with the first-order fragment Sigma2. Our main contribution is that deterministic partially ordered two-way B"uchi automata are expressively complete for the first-order fragment Delta2. As an intermediate step, we show that deterministic partially ordered two-way B"uchi 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"uchi automata.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Partially ordered two-way Büchi automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3073637)