Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2672
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKufleitner, Manfredde
dc.contributor.authorLauser, Alexanderde
dc.date.accessioned2010-07-14de
dc.date.accessioned2016-03-31T07:58:56Z-
dc.date.available2010-07-14de
dc.date.available2016-03-31T07:58:56Z-
dc.date.issued2010de
dc.identifier.other326057005de
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-55082de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/2689-
dc.identifier.urihttp://dx.doi.org/10.18419/opus-2672-
dc.description.abstractWe 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.en
dc.language.isoende
dc.relation.ispartofseriesTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2010,3de
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.classificationBüchi-Automat , Mathematische Logikde
dc.subject.ddc004de
dc.titlePartially ordered two-way Büchi automataen
dc.typeworkingPaperde
dc.date.updated2013-07-16de
ubs.fakultaetFakultät Informatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
ubs.opusid5508de
ubs.publikation.typArbeitspapierde
ubs.schriftenreihe.nameTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnikde
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.