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

DOI10.1016/J.JCSS.2014.04.007MaRDI QIDQ2453584zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Characterizing definability of second-order generalized quantifiers
• Definability of second order generalized quantifiers
• The hierarchy theorem for generalized quantifiers
• The hierarchy theorem for second order generalized quantifiers
• Definability hierarchies of generalized quantifiers

Cites work

• scientific article; zbMATH DE number 5836323 (Why is no real title available?)
• scientific article; zbMATH DE number 6003856 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 1734460 (Why is no real title available?)
• scientific article; zbMATH DE number 1841830 (Why is no real title available?)
• scientific article; zbMATH DE number 1453076 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• A logical characterization of the counting hierarchy
• A remark on collective quantification
• A uniform approach to define complexity classes
• Definability of second order generalized quantifiers
• Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents
• Extensions of MSO and the monadic counting hierarchy
• Finite automata with generalized acceptance criteria
• First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
• Lindström quantifiers and leaf language definability
• On a generalization of quantifiers
• On second-order generalized quantifiers and finite structures
• On uniformity within \(NC^ 1\)
• Parallel computation with threshold functions
• Parity, circuits, and the polynomial-time hierarchy
• Relating polynomial time to constant depth
• Rudimentary Languages and Second‐Order Logic
• The hierarchy theorem for second order generalized quantifiers
• The polynomial-time hierarchy
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(3)

• Characterizing definability of second-order generalized quantifiers
• Dependence logic with a majority quantifier
• Definability of second order generalized quantifiers

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

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