Counting quantifiers, successor relations, and logarithmic space
Kousha Etessami · 2002
We present new expressibility lower bounds for a logic with a weak form of ordering using model theoretic games. Our lower bound is on first-order logic augmented with counting quantifiers, a logical language that over structures with a total-ordering has exactly the power of the class TC/sup 0/. We prove that it cannot express a property ORD in L, over structures with a successor relation. This holds even in light of the fact that the class L itself has a logical characterization as the properties expressible in first-order logic with a deterministic transitive closure operator over structures with a successor relation. The proof uses an extension of the well known Ehrenfeucht-Fraisse Games for logics with counting. We also show that ORD is actually complete for L (via quantifier free projections), and this fact is of independent interest.