The Data Complexity of the Syllogistic Fragments of English

Revised Selected Papers of the 17th Amsterdam Colloquium on Logic, Language and Meaning (AC 2009). Volume 6042 of Lecture Notes in Artificial Intelligence. 2009.

Pratt and Third's syllogistic fragments of English can be used to capture, in addition to syllogistic reasoning, many other kinds of common sense reasoning, and, in particular (i) knowledge base consistency and (ii) knowledge base query answering, modulo their FO semantic representations. We show how difficult, in terms of semantic (computational) complexity and data complexity (i.e., computational complexity the number of instances declared in a knowledge base), such reasoning problems are. In doing so, we pinpoint also those fragments for which the reasoning problems are tractable (in PTime) or intractable (NP-hard or coNP-hard).

@inproceedings{AC-2009,
   title = "The Data Complexity of the Syllogistic Fragments of English",
   year = "2009",
   author = "Camilo Thorne and Diego Calvanese",
   booktitle = "Revised Selected Papers of the 17th Amsterdam Colloquium on
Logic, Language and Meaning (AC 2009)",
   pages = "114--123",
   volume = "6042",
   publisher = "Springer",
   series = "Lecture Notes in Artificial Intelligence",
   doi = "10.1007/978-3-642-14287-1_12",
}