Computational complexity of the semantics of some natural language constructions

DOI10.1016/J.APAL.2003.11.016MaRDI QIDQ598312zbMATH OpenOpenAlexFDO

Authors Marcin Mostowski, Dominika Wojtyniak

Publication date 6 August 2004

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2003.11.016

zbMATH Keywords

Church's ThesisEdmond's ThesisHenkin quantifiersNP-completenessPTIME

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Logic of natural languages (03B65) Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)

Recommendations

• More fragments of language.
• Fragments of language
• Computational consequences of agreement and ambiguity in natural language
• Computational complexity of syntactic agreement and lexical ambiguity
• Henkin quantifiers and complete problems

Cites work

• Comments on Jaakko Hintikka's paper "Quantifiers vs. Quantification theory"
• Degrees of logics with Henkin quantifiers in poor vocabularies
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1163935 (Why is no real title available?)
• scientific article; zbMATH DE number 3196255 (Why is no real title available?)
• On branching quantifiers in English
• Paths, Trees, and Flowers
• Quantifiers vs. Quantification Theory

Cited in

(17)

• A remark on collective quantification
• The computational complexity of ideal semantics
• Computational complexity of terminological reasoning in BACK
• Interactive semantic alignment model: social influence and local transmission bottleneck
• Computational consequences of agreement and ambiguity in natural language
• Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents
• Natural language semantics and computability
• On the complexity of semantic self-minimization
• A dichotomy result for Ramsey quantifiers
• The Computational Complexity of Quantified Reciprocals
• scientific article; zbMATH DE number 140381 (Why is no real title available?)
• On Syntactic versus Computational Views of Approximability
• scientific article; zbMATH DE number 1405451 (Why is no real title available?)
• Logic and complexity in cognitive science
• Characterizing polynomial Ramsey quantifiers
• 2006 Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '06
• A remark on Henkin sentences and their contraries

This page was built for publication: Computational complexity of the semantics of some natural language constructions

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