On the computational complexity of the numerically definite syllogistic and related logics

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)
DOI 10.2178/bsl/1208358842
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 34,373
External links

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.

Add more references

Citations of this work BETA

A System of Relational Syllogistic Incorporating Full Boolean Reasoning.Nikolay Ivanov & Dimiter Vakarelov - 2012 - Journal of Logic, Language and Information 21 (4):433-459.
The Syllogistic with Unity.Ian Pratt-Hartmann - 2013 - Journal of Philosophical Logic 42 (2):391-407.

Add more citations

Similar books and articles

Lewis Dichotomies in Many-Valued Logics.Simone Bova - 2012 - Studia Logica 100 (6):1271-1290.
Fragments of Language.Ian Pratt-Hartmann - 2004 - Journal of Logic, Language and Information 13 (2):207-223.
A System of Relational Syllogistic Incorporating Full Boolean Reasoning.Nikolay Ivanov & Dimiter Vakarelov - 2012 - Journal of Logic, Language and Information 21 (4):433-459.
Complexity of the Two-Variable Fragment with Counting Quantifiers.Ian Pratt-Hartmann - 2005 - Journal of Logic, Language and Information 14 (3):369-395.
The Syllogistic with Unity.Ian Pratt-Hartmann - 2013 - Journal of Philosophical Logic 42 (2):391-407.
Branching-Time Logics Repeatedly Referring to States.Volker Weber - 2009 - Journal of Logic, Language and Information 18 (4):593-624.
On the Restraining Power of Guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
Two Variable First-Order Logic Over Ordered Domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
Syllogistic Logic with Comparative Adjectives.Lawrence S. Moss - 2011 - Journal of Logic, Language and Information 20 (3):397-417.
The Complexity of Hybrid Logics Over Equivalence Relations.Martin Mundhenk & Thomas Schneider - 2009 - Journal of Logic, Language and Information 18 (4):493-514.
Logics for the Relational Syllogistic.Ian Pratt-hartmann & Lawrence S. Moss - 2009 - Review of Symbolic Logic 2 (4):647-683.
A Reconstruction of Aristotle's Modal Syllogistic.Marko Malink - 2006 - History and Philosophy of Logic 27 (2):95-141.

Analytics

Added to PP index
2010-08-30

Total downloads
12 ( #444,479 of 2,266,766 )

Recent downloads (6 months)
2 ( #210,371 of 2,266,766 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature