Computational complexity of the semantics of some natural language constructions

DOI10.1016/j.apal.2003.11.016zbMath1049.03025OpenAlexW1991317290MaRDI QIDQ598312

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

NP-completenessChurch's ThesisEdmond's ThesisHenkin quantifiersPTIME

Mathematics Subject Classification ID

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

Related Items (8)

A Dichotomy Result for Ramsey Quantifiers ⋮ Interactive semantic alignment model: social influence and local transmission bottleneck ⋮ Characterizing polynomial Ramsey quantifiers ⋮ Easy solutions for a hard problem? The computational complexity of reciprocals with quantificational antecedents ⋮ 2006 Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '06 ⋮ A remark on collective quantification ⋮ The Computational Complexity of Quantified Reciprocals ⋮ Logic and Complexity in Cognitive Science

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On branching quantifiers in English
• Degrees of logics with Henkin quantifiers in poor vocabularies
• Quantifiers vs. Quantification Theory
• Comments on Jaakko Hintikka's paper "Quantifiers vs. Quantification theory"
• Paths, Trees, and Flowers

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