Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents

DOI10.1007/S10849-013-9181-9MaRDI QIDQ2255227zbMATHOpenAlexFDO

Authors Fabian Schlotterbeck, Oliver Bott

Publication date 9 February 2015

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

Full work available at URL https://doi.org/10.1007/s10849-013-9181-9

zbMATH Keywords

computational complexityexperimental semanticsreciprocal sentences

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Linguistics (91F20)

Recommendations

• scientific article; zbMATH DE number 3845566
• The complexity of satisfaction problems in reverse mathematics
• The Complexity of Satisfaction Problems in Reverse Mathematics
• On the complexity of computation of rudimentary predicates
• A characterization of the complexity of recursive predicates
• scientific article; zbMATH DE number 3336809
• scientific article; zbMATH DE number 1088223
• The quantifier complexity of NF
• The Complexity of Counting Quantifiers on Equality Languages

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1884382 (Why is no real title available?)
• A remark on collective quantification
• Computational Complexity
• Computational complexity of the semantics of some natural language constructions
• Essays in logical semantics
• Fragments of language
• Henkin quantifiers: logic, games, and computation.
• Logic and complexity in cognitive science
• More fragments of language.
• On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics
• Quantifiers vs. Quantification Theory
• Reachability is harder for directed than for undirected finite graphs
• Reducibility among combinatorial problems
• The computational complexity of probabilistic inference using Bayesian belief networks
• Tractable competence

Cited in

(5)

• The Computational Complexity of Quantified Reciprocals
• Characterizing polynomial Ramsey quantifiers
• A dichotomy result for Ramsey quantifiers
• Logic and complexity in cognitive science
• A characterization of definability of second-order generalized quantifiers with applications to non-definability

This page was built for publication: Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents

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