Technischer Bericht TR-2010-03

Bibliograph.
Daten
Kufleitner, Manfred; Lauser, Alexander: Partially Ordered Two-way Büchi Automata.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2010/03.
12 Seiten, englisch.
CR-Klassif.F.1.1 (Models of Computation)
F.4.1 (Mathematical Logic)
Keywordsinfinite words; two-way Büchi automaton; first-order logic
Kurzfassung

We introduce partially ordered two-way Büchi automata over infinite words. As for finite words, the nondeterministic variant recognizes the fragment Sigma2 of first-order logic FO[<] and the deterministic version yields the Delta2-definable omega-languages. As a byproduct of our results, we show that deterministic partially ordered two-way Büchi automata are effectively closed under Boolean operations.

In addition, we have coNP-completeness results for the emptiness problem and the inclusion problem over deterministic partially ordered two-way Büchi automata.

The results of this paper are presented at CIAA 2010.

Volltext und
andere Links
PDF (441734 Bytes)
PostScript (811000 Bytes)
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
Eingabedatum14. Juni 2010
   Publ. Institut   Publ. Informatik