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

Bulletin of Symbolic Logic 14 (1):1-28 (2008)
  Copy   BIBTEX

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

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 103,449

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Fragments of first-order logic.Ian Pratt-Hartmann - 2023 - Oxford: Oxford University Press.
Complexity Results of STIT Fragments.François Schwarzentruber - 2012 - Studia Logica 100 (5):1001-1045.
Fragments of language.Ian Pratt-Hartmann - 2004 - Journal of Logic, Language and Information 13 (2):207-223.
The guarded fragment with transitive guards.Wiesław Szwast & Lidia Tendera - 2004 - Annals of Pure and Applied Logic 128 (1-3):227-276.
Logics for the relational syllogistic.Ian Pratt-Hartmann & Lawrence S. Moss - 2009 - Review of Symbolic Logic 2 (4):647-683.

Analytics

Added to PP
2010-08-30

Downloads
82 (#264,102)

6 months
15 (#168,777)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Extended Syllogistics in Calculus CL.Jens Lemanski - 2020 - Journal of Applied Logics 8 (2):557-577.
The Syllogistic with Unity.Ian Pratt-Hartmann - 2013 - Journal of Philosophical Logic 42 (2):391-407.
A System of Relational Syllogistic Incorporating Full Boolean Reasoning.Nikolay Ivanov & Dimiter Vakarelov - 2012 - Journal of Logic, Language and Information 21 (4):433-459.
Decidable first-order modal logics with counting quantifiers.Christopher Hampson - 2016 - In Lev Beklemishev, Stéphane Demri & András Máté, Advances in Modal Logic, Volume 11. CSLI Publications. pp. 382-400.

Add more citations

References found in this work

Numerical Term Logic.Wallace A. Murphree - 1998 - Notre Dame Journal of Formal Logic 39 (3):346-362.
The Numerical Syllogism and Existential Presupposition.Wallace A. Murphree - 1997 - Notre Dame Journal of Formal Logic 38 (1):49-64.
Pure numerical Boolean syllogisms.Edward A. Hacker & William Tuthill Parry - 1967 - Notre Dame Journal of Formal Logic 8 (4):321-324.
On the logic of "few", "many", and "most".Philip L. Peterson - 1979 - Notre Dame Journal of Formal Logic 20 (1):155-179.

View all 11 references / Add more references