om Quantifiers and Leaf Language Definability
Fachbereich Informatik, Heribert Vollmer, Theoretische Informatik · 1996
We show that examinations of the expressive power of logical formulae enriched by Lindstr¨ om 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 Lindstr¨ om 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