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

DOI10.1016/J.JCSS.2014.04.007zbMATH Open1327.03030OpenAlexW2082972831MaRDI QIDQ2453584FDOQ2453584

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

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

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)

Cites Work

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

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)