David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Logic, Language and Information 13 (2):207-223 (2004)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Nikolay Ivanov & Dimiter Vakarelov (2012). A System of Relational Syllogistic Incorporating Full Boolean Reasoning. Journal of Logic, Language and Information 21 (4):433-459.
Ian Pratt-hartmann & Lawrence S. Moss (2009). Logics for the Relational Syllogistic. Review of Symbolic Logic 2 (4):647-683.
Fabian Schlotterbeck & Oliver Bott (2013). Easy Solutions for a Hard Problem? The Computational Complexity of Reciprocals with Quantificational Antecedents. Journal of Logic, Language and Information 22 (4):363-390.
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 downloads17 ( #147,710 of 1,700,362 )
Recent downloads (6 months)7 ( #88,892 of 1,700,362 )
How can I increase my downloads?