Dichotomy result for independence-friendly prefixes of generalized quantifiers

DOI10.1017/JSL.2013.30MaRDI QIDQ5177884zbMATH OpenOpenAlexFDO

Authors Merlijn Sevenster

Publication date 6 March 2015

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/jsl.2013.30

zbMATH Keywords

branching quantifiersdescriptive complexitydichotomyHenkin quantifiersindependence-friendly logicNP hardness

Mathematics Subject Classification ID

Other nonclassical logic (03B60) Logic with extra quantifiers and operators (03C80) Complexity of computation (including implicit computational complexity) (03D15) Descriptive complexity and finite models (68Q19)

Recommendations

• Complexity of syntactical tree fragments of independence-friendly logic
• A dichotomy result for Ramsey quantifiers
• ON EXISTENTIAL DECLARATIONS OF INDEPENDENCE IN IF LOGIC
• Independence-friendly logic without Henkin quantification
• Computer Science Logic

Cites work

• A course in game theory.
• Compositional semantics for a language of imperfect information
• Existential second-order logic over graphs: charting the tractability frontier
• Finite Partially‐Ordered Quantifiers
• Generalized quantifiers in dependence logic
• Henkin quantifiers and complete problems
• Independence-friendly logic. A game-theoretic approach
• ON EXISTENTIAL DECLARATIONS OF INDEPENDENCE IN IF LOGIC
• On the logic of informational independence and its applications
• On the Structure of Polynomial Time Reducibility

Cited in

(7)

• Cooperation in games and epistemic readings of independence-friendly sentences
• Complexity of syntactical tree fragments of independence-friendly logic
• A dichotomy result for Ramsey quantifiers
• Modeling Monty Hall in IF logic
• SOME OBSERVATIONS ABOUT GENERALIZED QUANTIFIERS IN LOGICS OF IMPERFECT INFORMATION
• Characterizing polynomial Ramsey quantifiers
• Independence-friendly logic without Henkin quantification

This page was built for publication: Dichotomy result for independence-friendly prefixes of generalized quantifiers

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