Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1834
URN: urn:nbn:de:0030-drops-18345
URL: https://drops.dagstuhl.de/opus/volltexte/2009/1834/
Bojanczyk, Mikolaj
Weak MSO with the Unbounding Quantifier
| pdf-format: |
|
Abstract
A new class of languages of infinite words is introduced, called the \emph{max-regular languages}, extending the class of $\omega$-regular languages. The class has two equivalent descriptions: in terms of automata (a type of deterministic counter automaton), and in terms of logic (weak monadic second-order logic with a bounding quantifier). Effective translations between the logic and automata are given.
BibTeX - Entry
@InProceedings{bojanczyk:LIPIcs:2009:1834,
author = {Mikolaj Bojanczyk},
title = {{Weak MSO with the Unbounding Quantifier}},
booktitle = {26th International Symposium on Theoretical Aspects of Computer Science},
pages = {159--170},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-09-5},
ISSN = {1868-8969},
year = {2009},
volume = {3},
editor = {Susanne Albers and Jean-Yves Marion},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/1834},
URN = {urn:nbn:de:0030-drops-18345},
doi = {10.4230/LIPIcs.STACS.2009.1834},
annote = {Keywords: Automata, Monadic second-order logic}
}
| Keywords: | Automata, Monadic second-order logic | |
| Seminar: | 26th International Symposium on Theoretical Aspects of Computer Science | |
| Issue date: | 2009 | |
| Date of publication: | 19.02.2009 |
