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

DOI10.1007/S10849-013-9181-9zbMATH Open1305.68094OpenAlexW1986360923MaRDI QIDQ2255227FDOQ2255227

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

Recommendations

• scientific article
• 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

zbMATH Keywords

computational complexityexperimental semanticsreciprocal sentences

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Quantifiers vs. Quantification Theory
• Computational Complexity
• Essays in logical semantics
• Reachability is harder for directed than for undirected finite graphs
• The computational complexity of probabilistic inference using Bayesian belief networks
• Tractable competence
• Title not available (Why is that?)
• A remark on collective quantification
• Henkin quantifiers: logic, games, and computation.
• Computational complexity of the semantics of some natural language constructions
• More fragments of language.
• Fragments of language
• Logic and Complexity in Cognitive Science
• On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics

Cited In (5)

• The Computational Complexity of Quantified Reciprocals
• Logic and Complexity in Cognitive Science
• Characterizing polynomial Ramsey quantifiers
• A Dichotomy Result for Ramsey Quantifiers
• 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)