TY - GEN
T1 - The data complexity of the syllogistic fragments of english
AU - Thorne, Camilo
AU - Calvanese, Diego
PY - 2010
Y1 - 2010
N2 - 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 w.r.t. 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).
AB - 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 w.r.t. 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).
UR - http://www.scopus.com/inward/record.url?scp=77958476102&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-14287-1_12
DO - 10.1007/978-3-642-14287-1_12
M3 - Contribución a la conferencia
AN - SCOPUS:77958476102
SN - 3642142869
SN - 9783642142864
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 114
EP - 123
BT - Logic, Language and Meaning - 17th Amsterdam Colloquium, Revised Selected Papers
T2 - 17th Amsterdam Colloquium on Logic, Language and Meaning
Y2 - 16 December 2009 through 18 December 2009
ER -