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)
|
Keywords | infinite 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
|
Eingabedatum | 14. Juni 2010 |
---|