Monadic Second Order Definability as a Common Characterization of Finite Automata,Certain Classes of Programs and Logics

Abstract

We introduce the notion of monadic second order definability (m.s.o definability) of automata, programs and logics and point out some classes of automata (theorem 7), programs (theorem 8) and logics (theorem 9) which are m.s.o definable.