Monadic Second-Order Logic with Arbitrary Monadic Predicates

摘要

We study Monadic Second-Order Logic (MSO) over finite words, extended with (non-uniform arbitrary) monadic predicates. We show that it defines a class of languages that has algebraic, automata-theoretic, and machine-independent characterizations. We consider the regularity question: Given a language in this class, when is it regular? To answer this, we show a substitution property and the existence of a syntactical predicate.