Abstract:
We introduce second-order Lindstroem quantifiers and examine analogies to the concept of leaf language definability. The quantifier structure in a second-order sentence defining a language and the quantifier structure in a first-order sentence characterizing the appropriate leaf language correspond to one another. Under some assumptions, leaf language definability and definability with second-order Lindstroem quantifiers may be seen as equivalent. Along the way we tighten the best up to now known leaf language characterization of the classes of the polynomial time hierarchy and give a new model-theoretic characterization of PSPACE.

Abstract:
We show that examinations of the expressive power of logical formulae enriched by Lindstroem quantifiers over ordered finite structures have a well-studied complexity-theoretic counterpart: the leaf language approach to define complexity classes. Model classes of formulae with Lindstroem quantifiers are nothing else than leaf language definable sets. Along the way we tighten the best up to now known leaf language characterization of the classes of the polynomial time hierarchy and give a new model-theoretic characterization of PSPACE.