Fragments of language
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 | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesStéphane Demri & Hans De Nivelle (2005). Deciding Regular Grammar Logics with Converse Through First-Order Logic. Journal of Logic, Language and Information 14 (3).
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).
Savas Konur (forthcoming). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information.
Ian Pratt-Hartmann (2008). On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics. The 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.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2009-01-28Total downloads4 ( #178,675 of 549,087 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
