×

Eventual periodicity and “one-dimensional” queries. (English) Zbl 0768.03002

A generalization of the (finite version of the) Büchi-Ladner representation theorem for monadic second order Boolean queries on chainlike graphs is presented. A careful application of the monotonicity of one-dimensional least fixed point inductions results in the discovery that these inductions express fewer Boolean queries than even the monadic \(\Delta^ 1_ 1\) formulas.
Reviewer: G.L.McColm (Tampa)

MSC:

03B15 Higher-order logic; type theory (MSC2010)
68P15 Database theory
05C20 Directed graphs (digraphs), tournaments
03D05 Automata and formal grammars in connection with logical questions
Full Text: DOI