Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-2672
Langanzeige der Metadaten
DC Element | Wert | Sprache |
---|---|---|
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 |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
TR_2010_03.pdf | 431,38 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.