Lindström quantifiers and leaf language definability

DOI10.1142/S0129054198000180MaRDI QIDQ5248979zbMATH OpenOpenAlexFDO

Authors 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 complexityfinite model theorygeneralized quantifierleaf language definability

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1453080
• Definability of second order generalized quantifiers
• Logspace and logtime leaf languages
• scientific article; zbMATH DE number 2051828
• A characterization of the leaf language classes

Cites work

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

Cited in

(15)

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

This page was built for publication: Lindström quantifiers and leaf language definability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5248979)