ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR96-005 | 23rd February 1998 00:00

Lindstroem Quantifiers and Leaf Language Definability Revision of: TR96-005

RSS-Feed

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.


Paper:

TR96-005 | 9th January 1996 00:00

Lindstroem Quantifiers and Leaf Language Definability





TR96-005
Authors: Hans-Joerg Burtschick, Heribert Vollmer
Publication: 26th January 1996 15:59
Downloads: 590
Keywords: 


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.



ISSN 1433-8092 | Imprint