Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-2672
| Autor(en): | Kufleitner, Manfred Lauser, Alexander |
| Titel: | Partially ordered two-way Büchi automata |
| Erscheinungsdatum: | 2010 |
| Dokumentart: | Arbeitspapier |
| Serie/Report Nr.: | 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 |
| Zusammenfassung: | 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. |
| 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.