Counting Quantifiers, Successor Relations, and Logarithmic Space

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publicationProceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, June 19-22, 1995
Number of pages10
Publication statusPublished - Jun 1995


Dive into the research topics of 'Counting Quantifiers, Successor Relations, and Logarithmic Space'. Together they form a unique fingerprint.

Cite this