Graduate studies at Western
Journal of Logic, Language and Information 13 (2):207-223 (2004)
|Abstract||By a fragment of a natural language we mean a subset of thatlanguage equipped with semantics which translate its sentences intosome formal system such as first-order logic. The familiar conceptsof satisfiability and entailment can be defined for anysuch fragment in a natural way. The question therefore arises, for anygiven fragment of a natural language, as to the computational complexityof determining satisfiability and entailment within that fragment. Wepresent a series of fragments of English for which the satisfiabilityproblem is polynomial, NP-complete, EXPTIME-complete,NEXPTIME-complete and undecidable. Thus, this paper represents a casestudy in how to approach the problem of determining the logicalcomplexity of various natural language constructions. In addition, wedraw some general conclusions about the relationship between naturallanguage and formal logic.|
|Keywords||complexity computational generalized language natural quantifiers semantics|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Stéphane Demri & Hans De Nivelle (2005). Deciding Regular Grammar Logics with Converse Through First-Order Logic. Journal of Logic, Language and Information 14 (3):289-329.
Marcin Mostowski & Jakub Szymanik (2012). Semantic Bounds for Everyday Language. Semiotica 188 (1/4):363-372.
Patrick Suppes (1979). Logical Inference in English: A Preliminary Analysis. Studia Logica 38 (4):375 - 391.
Ian Pratt-Hartmann (2005). Complexity of the Two-Variable Fragment with Counting Quantifiers. Journal of Logic, Language and Information 14 (3):369-395.
Savas Konur (2011). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information 20 (1):49-68.
Ian Pratt-Hartmann (2008). On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics. Bulletin of Symbolic Logic 14 (1):1-28.
Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
Ian Pratt-Hartmann (2003). A Two-Variable Fragment of English. Journal of Logic, Language and Information 12 (1):13-45.
Added to index2009-01-28
Total downloads4 ( #189,291 of 740,419 )
Recent downloads (6 months)0
How can I increase my downloads?