Graduate studies at Western
Bulletin of Symbolic Logic 14 (1):1-28 (2008)
|Abstract||The numerically definite syllogistic is the fragment of English obtained by extending the language of the classical syllogism with numerical quantifiers. The numerically definite relational syllogistic is the fragment of English obtained by extending the numerically definite syllogistic with predicates involving transitive verbs. This paper investigates the computational complexity of the satisfiability problem for these fragments. We show that the satisfiability problem (= finite satisfiability problem) for the numerically definite syllogistic is strongly NP-complete, and that the satisfiability problem (= finite satisfiability problem) for the numerically definite relational syllogistic is NEXPTIME-complete, but perhaps not strongly so. We discuss the related problem of probabilistic (propositional) satisfiability, and thereby demonstrate the incompleteness of some proof-systems that have been proposed for the numerically definite syllogistic|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Simone Bova (2012). Lewis Dichotomies in Many-Valued Logics. Studia Logica 100 (6):1271-1290.
Peter Lohmann & Heribert Vollmer (2013). Complexity Results for Modal Dependence Logic. Studia Logica 101 (2):343-366.
Ian Pratt-Hartmann (2004). Fragments of Language. Journal of Logic, Language and Information 13 (2):207-223.
Nikolay Ivanov & Dimiter Vakarelov (2012). A System of Relational Syllogistic Incorporating Full Boolean Reasoning. Journal of Logic, Language and Information 21 (4):433-459.
Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
Ian Pratt-Hartmann (2005). Complexity of the Two-Variable Fragment with Counting Quantifiers. Journal of Logic, Language and Information 14 (3):369-395.
Ian Pratt-Hartmann (2013). The Syllogistic with Unity. Journal of Philosophical Logic 42 (2):391-407.
Volker Weber (2009). Branching-Time Logics Repeatedly Referring to States. Journal of Logic, Language and Information 18 (4):593-624.
Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
Martin Otto (2001). Two Variable First-Order Logic Over Ordered Domains. Journal of Symbolic Logic 66 (2):685-702.
Lawrence S. Moss (2011). Syllogistic Logic with Comparative Adjectives. Journal of Logic, Language and Information 20 (3):397-417.
Martin Mundhenk & Thomas Schneider (2009). The Complexity of Hybrid Logics Over Equivalence Relations. Journal of Logic, Language and Information 18 (4):493-514.
Ian Pratt-hartmann & Lawrence S. Moss (2009). Logics for the Relational Syllogistic. The Review of Symbolic Logic 2 (4):647-683.
Marko Malink (2006). A Reconstruction of Aristotle's Modal Syllogistic. History and Philosophy of Logic 27 (2):95-141.
Added to index2010-08-30
Total downloads2 ( #246,970 of 740,223 )
Recent downloads (6 months)1 ( #61,960 of 740,223 )
How can I increase my downloads?