Henkin quantifiers and complete problems
From MaRDI portal
Publication:1088983
DOI10.1016/0168-0072(86)90040-0zbMath0618.03016OpenAlexW1988735961WikidataQ56763808 ScholiaQ56763808MaRDI QIDQ1088983
Publication date: 1986
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2027.42/26312
first-order logic\({\mathcal N}{\mathcal P}\)-complete properties of finite structuresco-\({\mathcal N}{\mathcal P}\) propertiescomputational aspects of partially ordered quantificationHenkin qantifiers
Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Boolean dependence logic and partially-ordered connectives, The complexity class θp2: Recent results and applications in AI and modal logic, Inductive definitions over finite structures, Henkin and function quantifiers, Hierarchies in transitive closure logic, stratified Datalog and infinitary logic, Descriptive characterizations of computational complexity, Model-checking games for logics of imperfect information, A Dichotomy Result for Ramsey Quantifiers, Alternating (in)dependence-friendly logic, Equilibrium semantics of languages of imperfect information, Henkin quantifiers and Boolean formulae: a certification perspective of DQBF, Lottery semantics: a compositional semantics for probabilistic first-order logic with imperfect information, Characterizing polynomial Ramsey quantifiers, Generalized quantification as substructural logic, Relativized logspace and generalized quantifiers over finite ordered structures, Linear Programming Tools for Analyzing Strategic Games of Independence-Friendly Logic and Applications, Monadic partition logics and finite automata, Capturing complexity classes by fragments of second-order logic, A logical analysis of Monty Hall and Sleeping Beauty, Functional interpretations of linear and intuitionistic logic, Complexity of syntactical tree fragments of independence-friendly logic, 2006 Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '06, DICHOTOMY RESULT FOR INDEPENDENCE-FRIENDLY PREFIXES OF GENERALIZED QUANTIFIERS, On the computational consequences of independence in propositional logic, 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02, The Computational Complexity of Quantified Reciprocals, Games for Inclusion Logic and Fixed-Point Logic, Dependency Concepts up to Equivalence., IF-logic and truth-definition, Partially ordered connectives and monadic monotone strict NP, Partially interpreted relations and partially interpreted quantifiers, Succinctness as a source of complexity in logical formalisms, Good-for-Game QPTL: An Alternating Hodges Semantics
Cites Work
