Deterministic Automata and Extensions of Weak MSO

Authors Mikolaj Bojanczyk, Szymon Torunczyk



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2009.2308.pdf
  • Filesize: 212 kB
  • 12 pages

Document Identifiers

Author Details

Mikolaj Bojanczyk
Szymon Torunczyk

Cite AsGet BibTex

Mikolaj Bojanczyk and Szymon Torunczyk. Deterministic Automata and Extensions of Weak MSO. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2308

Abstract

We introduce a new class of automata on infinite words, called min-automata. We prove that min-automata have the same expressive power as weak monadic second-order logic (weak MSO) extended with a new quantifier, the recurrence quantifier. These results are dual to a framework presented in \cite{max-automata}, where max-automata were proved equivalent to weak MSO extended with an unbounding quantifier. We also present a general framework, which tries to explain which types of automata on infinite words correspond to extensions of weak MSO. As another example for the usefulness framework, apart from min- and max-automata, we define an extension of weak MSO with a quantifier that talks about ultimately periodic sets.
Keywords
  • Deterministic automata
  • Weak MSO
  • min-automata
  • max-automata
  • BS-automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail