Partially ordered two-way Büchi automata

Kufleitner, Manfred; Lauser, Alexander

Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2672

Full metadata record

DC Field	Value	Language
dc.contributor.author	Kufleitner, Manfred	de
dc.contributor.author	Lauser, Alexander	de
dc.date.accessioned	2010-07-14	de
dc.date.accessioned	2016-03-31T07:58:56Z	-
dc.date.available	2010-07-14	de
dc.date.available	2016-03-31T07:58:56Z	-
dc.date.issued	2010	de
dc.identifier.other	326057005	de
dc.identifier.uri	http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-55082	de
dc.identifier.uri	http://elib.uni-stuttgart.de/handle/11682/2689	-
dc.identifier.uri	http://dx.doi.org/10.18419/opus-2672	-
dc.description.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.	en
dc.language.iso	en	de
dc.relation.ispartofseries	Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2010,3	de
dc.rights	info:eu-repo/semantics/openAccess	de
dc.subject.classification	Büchi-Automat , Mathematische Logik	de
dc.subject.ddc	004	de
dc.title	Partially ordered two-way Büchi automata	en
dc.type	workingPaper	de
dc.date.updated	2013-07-16	de
ubs.fakultaet	Fakultät Informatik, Elektrotechnik und Informationstechnik	de
ubs.institut	Institut für Formale Methoden der Informatik	de
ubs.opusid	5508	de
ubs.publikation.typ	Arbeitspapier	de
ubs.schriftenreihe.name	Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik	de
Appears in Collections:	05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:

File	Description	Size	Format
TR_2010_03.pdf		431,38 kB	Adobe PDF	View/Open

Show simple item record

University of Stuttgart

OPUS - Publication Server of the University of Stuttgart