A characterization of definability of second-order generalized quantifiers with applications to non-definability

DOI10.1016/j.jcss.2014.04.007zbMath1327.03030OpenAlexW2082972831MaRDI QIDQ2453584

Juha Kontinen, Jakub Szymanik

Publication date: 10 June 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.04.007

zbMATH Keywords

definabilitysecond-order logicmajority quantifiersecond-order generalized quantifierscollective quantification

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Second- and higher-order model theory (03C85) Interpolation, preservation, definability (03C40)

Related Items (1)

Dependence logic with a majority quantifier

Cites Work

• Extensions of MSO and the monadic counting hierarchy
• Definability of second order generalized quantifiers
• A remark on collective quantification
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Parallel computation with threshold functions
• A uniform approach to define complexity classes
• The polynomial-time hierarchy
• Relating polynomial time to constant depth
• On second-order generalized quantifiers and finite structures
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents
• On uniformity within \(NC^ 1\)
• On a generalization of quantifiers
• Parity, circuits, and the polynomial-time hierarchy
• Rudimentary Languages and Second‐Order Logic
• LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
• A logical characterization of the counting hierarchy
• The hierarchy theorem for second order generalized quantifiers
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A characterization of definability of second-order generalized quantifiers with applications to non-definability