Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2672
Authors: Kufleitner, Manfred
Lauser, Alexander
Title: Partially ordered two-way Büchi automata
Issue Date: 2010
metadata.ubs.publikation.typ: Arbeitspapier
Series/Report no.: Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2010,3
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-55082
http://elib.uni-stuttgart.de/handle/11682/2689
http://dx.doi.org/10.18419/opus-2672
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.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
TR_2010_03.pdf431,38 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.