Deterministic Automata and Extensions of Weak MSO

Mikołaj Bojańczyk, Szymon Toruńczyk

DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2009 · 15 citations · 3 references

DOIFull text

Open access

Concepts

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.

References

3