On the Complexity of the Numerically Definite Syllogistic and Related Fragments

Abstract

In this paper, we determine the complexity of the satisfiability problem for various logics obtained by adding numerical quantifiers, and other constructions, to the traditional syllogistic. In addition, we demonstrate the incompleteness of some recently proposed proof-systems for these logics.

24 pages 1 figure

References in corpus (2)

• Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers
• Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers

Cited by in corpus (5)

• A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
• A system of relational syllogistic incorporating full Boolean reasoning
• Interleaving Logic and Counting
• Ontology Focusing: Knowledge-enriched Databases on Demand
• The Syllogistic with Unity