2010 | OriginalPaper | Buchkapitel
The Data Complexity of the Syllogistic Fragments of English
verfasst von : Camilo Thorne, Diego Calvanese
Erschienen in: Logic, Language and Meaning
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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).