LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY

DOI10.1142/S0129054198000180zbMath1319.68104OpenAlexW1983193342MaRDI QIDQ5248979

Hans-Jörg Burtschick, Heribert Vollmer

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054198000180

zbMATH Keywords

computational complexitygeneralized quantifierfinite model theoryleaf language definability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (15)

Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies ⋮ Dependence logic with a majority quantifier ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Unnamed Item ⋮ On Second-Order Monadic Groupoidal Quantifiers ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ The descriptive complexity approach to LOGCFL ⋮ Machines that can output empty words ⋮ A remark on collective quantification ⋮ THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS ⋮ On Existentially First-Order Definable Languages and Their Relation to NP ⋮ SOME OBSERVATIONS ABOUT GENERALIZED QUANTIFIERS IN LOGICS OF IMPERFECT INFORMATION ⋮ A reducibility for the dot-depth hierarchy

Cites Work

• Succinct circuit representations and leaf language classes are basically the same concept
• A uniform approach to define complexity classes
• The polynomial-time hierarchy
• Logspace and logtime leaf languages
• On uniformity within \(NC^ 1\)
• On balanced versus unbalanced computation trees

This page was built for publication: LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY