Document Open Access Logo

Deterministic Automata and Extensions of Weak MSO

Authors Mikolaj Bojanczyk, Szymon Torunczyk

PDF

File

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

Document Identifiers

Subject Classification

Keywords
  • Deterministic automata
  • Weak MSO
  • min-automata
  • max-automata
  • BS-automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get 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

Author Details

Mikolaj Bojanczyk
Szymon Torunczyk
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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact