Kufleitner, ManfredLauser, Alexander2010-07-142016-03-312010-07-142016-03-312010326057005http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-55082http://elib.uni-stuttgart.de/handle/11682/2689http://dx.doi.org/10.18419/opus-2672We 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.eninfo:eu-repo/semantics/openAccessBüchi-Automat , Mathematische Logik004workingPaper2013-07-16