Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with generalizedquantifiers:
TR96-005 | 9th January 1996
Hans-Joerg Burtschick, Heribert Vollmer

Lindstroem Quantifiers and Leaf Language Definability

Revisions: 1

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 ... more >>>

ISSN 1433-8092 | Imprint