| Bibliography | Kufleitner, Manfred; Lauser, Alexander: Partially Ordered Two-way Büchi Automata.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Technical Report Computer Science No. 2010/03.
12 pages, english.
|
|---|
| CR-Schema | F.1.1 (Models of Computation)
F.4.1 (Mathematical Logic)
|
|---|
| Keywords | infinite words; two-way Büchi automaton; first-order logic |
|---|
| Abstract | 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.
|
|---|
Full text and
other links | PDF (441734 Bytes)
PostScript (811000 Bytes)
|
|---|
| Department(s) | University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
|
|---|
| Entry date | June 14, 2010 |
|---|