Eventual periodicity and ``one-dimensional'' queries.
Gregory L. McColm · Notre Dame Journal of Formal Logic · 1992
We expand on the automata-like behavior of monadic second order relations investigated by Buchi and Ladner.We present a generalization of their representation theorem and use it to separate the intersection of the classes of monadic existential second order and monadic universal second order queries from the class of one-dimensional inductive queries.