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 |