Dependence logic with a majority quantifier

DOI10.1007/s10849-015-9218-3zbMath1368.03040OpenAlexW2110257077MaRDI QIDQ302214

Heribert Vollmer, Arnaud Durand, Juha Kontinen, Johannes Ebbing

Publication date: 4 July 2016

Published in: Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2011/3346/

zbMATH Keywords

second-order logicexpressivitycomplexity theorymajoritydependencedependence logicteam semanticscounting hierarchydependence atom

Mathematics Subject Classification ID

Related Items (4)

CHARACTERIZING DOWNWARDS CLOSED, STRONGLY FIRST-ORDER, RELATIVIZABLE DEPENDENCIES ⋮ Expressivity and Complexity of Dependence Logic ⋮ Counting of Teams in First-Order Team Logics ⋮ SOME OBSERVATIONS ABOUT GENERALIZED QUANTIFIERS IN LOGICS OF IMPERFECT INFORMATION

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extensions of MSO and the monadic counting hierarchy
• Inclusion and exclusion dependencies in team semantics -- on some logics of imperfect information
• On definability in dependence logic
• From IF to BI. A tale of dependence and separation
• Definability of second order generalized quantifiers
• The complexity of combinatorial problems with succinct input representation
• Polynomial-time 1-Turing reductions from \(\#\)PH to \(\#\)P
• On second-order generalized quantifiers and finite structures
• Dependence and independence
• Expressing second-order sentences in intuitionistic dependence logic
• Complexity results for modal dependence logic
• Generalized quantifiers in dependence logic
• A characterization of definability of second-order generalized quantifiers with applications to non-definability
• Dependence logic with a majority quantifier
• PP is as Hard as the Polynomial-Time Hierarchy
• Model-theoretic and Computational Properties of Modal Dependence Logic
• Complexity classes defined by counting quantifiers
• Characterizing quantifier extensions of dependence logic
• LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY
• A logical characterization of the counting hierarchy
• The hierarchy theorem for second order generalized quantifiers
• Finite Model Theory

This page was built for publication: Dependence logic with a majority quantifier