LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
Authors:
- 1 September 1998
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 09 (03) , 277-294
Abstract
We introduce second-order Lindström 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 Lindström 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.Keywords
This publication has 6 references indexed in Scilit:
- Succinct circuit representations and leaf language classes are basically the same conceptInformation Processing Letters, 1996
- On balanced versus unbalanced computation treesTheory of Computing Systems, 1996
- Logspace and Logtime Leaf LanguagesInformation and Computation, 1996
- A uniform approach to define complexity classesTheoretical Computer Science, 1992
- On uniformity within NC1Journal of Computer and System Sciences, 1990
- The polynomial-time hierarchyTheoretical Computer Science, 1976