2026-07-20T11:45:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2308 2024-03-06T10:33:16Z ddc:004 open_access

Deterministic Automata and Extensions of Weak MSO Bojanczyk, Mikolaj Torunczyk, Szymon Deterministic automata Weak MSO min-automata max-automata BS-automata 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikolaj Bojanczyk and Szymon Torunczyk 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2308 urn:nbn:de:0030-drops-23081 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2308 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode