文章基本信息

标题：Lindstroem Quantifiers and Leaf Language Definability
本地全文：下载
作者：Hans-Joerg Burtschick ; Heribert Vollmer
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.