zbMATH — the first resource for mathematics

Computational complexity of terminological reasoning in BACK. (English) Zbl 0646.68110
Summary: Terminological reasoning is a mode of reasoning all hybrid knowledge representation systems based on KL-ONE rely on. After a short introduction of what terminological reasoning amounts to, it is proven that a complete inference algorithm for the BACK system would be computationally intractable. Interestingly, this result also applies to the KANDOR system, which had been conjectured to realize complete terminological inferences with a tractable algorithm. More generally, together with an earlier paper of Brachman and Levesque it shows that terminological reasoning is intractable for any system using a nontrivial description language. Finally, consequences of this distressing result are briefly discussed.
Reviewer: Reviewer (Berlin)

68T99 Artificial intelligence
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Allen, J.F., Maintaining knowledge about temporal intervals, Commun. ACM, 26, 11, 832-843, (1983) · Zbl 0519.68079
[2] Brachman, R.J., On the epistomological status of semantic networks, (), 3-50
[3] Brachman, R.J.; Levesque, H.J., The tractability of subsumption in frame-based description languages, (), 34-37
[4] Brachman, R.J.; Schmolze, J.G., An overview of the KL-ONE knowledge representation system, Cognitive sci., 9, 2, 171-216, (1985)
[5] Brachman, R.J.; Pigman Gilbert, V.; Levesque, H.J., An essential hybrid reasoning system: knowledge and symbol level accounts in KRYPTON, (), 532-539
[6] Brachman, R.J.; Fikes, R.E.; Levesque, H.J., KRYPTON: A functional approach to knowledge representation, (), IEEE computer, 16, 10, 67-73, (1983), a revised version of an article published
[7] Edelmann, J.; Owsnicki, B., Data models in knowledge representation systems: A case study, (), 69-74
[8] Garey, M.R.; Johnson, D.S., Computers and intractability—A guide to the theory of NP-completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[9] Kaczmarek, T.; Bates, R.; Robins, G., Recent developments in NIKL, (), 978-987
[10] Lovasz, L., Coverings and colorings of hypergraphs, (), 3-12
[11] Levesque, H.J., Making believers out of computers, computers and thought lecture at IJCAI-85, Los Angeles, CA, Artificial intelligence, 30, 1, 81-108, (1986)
[12] Lipkis, T., A KL-ONE classifier, (), 128-145
[13] Luck, K.von; Nebel, B.; Peltason, C.; Schmiedel, A., The anatomy of the BACK system, ()
[14] McAllester, D.A., Reasoning utility package User’s manual, ()
[15] McDermott, D., Tarskian semantics, or no notation without denotation!, Cognitive sci., 2, 3, 277-282, (1978)
[16] Patel-Schneider, P.F., Small can be beautiful in knowledge representation, (), 11-16
[17] Patel-Schneider, P.F., A four-valued semantics for frame-based description languages, (), 344-348
[18] Patel-Schneider, P.F., Decidable, logic-based knowledge representation, () · Zbl 1341.03037
[19] Schmolze, J.G.; Israel, D.J., KL-ONE: semantics and classification, (), 27-39
[20] Sondheimer, N.K.; Nebel, B., A logical-form and knowledge-base design for natural language generation, (), 612-618
[21] Vilain, M.B., The restricted language architecture of a hybrid representation system, (), 547-551
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.