zbMATH — the first resource for mathematics

Terminological reasoning is inherently intractable. (English) Zbl 0717.68089
Summary: Computational tractability has been a major concern in the area of terminological knowledge representation and reasoning. However, all analyses of the computational complexity of terminological reasoning are based on the hidden assumption that subsumption in terminologies reduces to subsumption of concept descriptons without a significant increase in computational complexity. It will be shown that this assumption, which seems to work in the “normal case”, is nevertheless wrong. Subsumption in terminologies turns out to be co-NP-complete for a minimal terminological representation language that is a subset of every useful terminological language.
Reviewer: Reviewer (Berlin)

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
68T30 Knowledge representation
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Borgida, A.; Brachman, R. J.; McGuinness, D. L.; Resnick, L. A., CLASSIC: A structural data model for objects, (Proceedings 1989 ACM SIGMOD International Conference on Management of Data, Portland, OR, (1989)), 59-67
[2] Brachman, R. J.; Borgida, A.; McGuinness, D. L.; Resnick, L. A., The CLASSIC knowledge representation system, or, KL-ONE: the next generation, (Preprints Workshop on Formal Aspects of Semantic Networks, Two Harbors, CA, (1989))
[3] Brachman, R. J.; Levesque, H. J., The tractability of subsumption in frame-based description languages, (Proceedings AAAI-84, Austin, TX, (1984)), 34-37
[4] Brachman, R. J.; Gilbert, V. Pigman; Levesque, H. J., An essential hybrid reasoning system: knowledge and symbol level accounts in KRYPTON, (Proceedings IJCAI-85, Los Angeles, CA, (1985)), 532-539
[5] Brachman, R. J.; Schmolze, J. G., An overview of the KL-ONE knowledge representation system, Cognitive Sci., 9, 171-216, (1985)
[6] Dörre, J.; Eisele, A., Determining consistency of feature terms with distributed disjunctions, (Metzing, D., GWAI-89, 13th German Workshop on Artificial Intelligence, (1989), Springer Berlin), 270-279
[7] Doyle, J.; Patil, R. S., Language restrictions, taxonomic classifications, and the utility of representation services, (Tech. Memo MIT/LCS/TM-387, (1989), Laboratory for Computer Science, MIT Cambridge, MA)
[8] Edelmann, J.; Owsnicki, B., Data models in knowledge representation systems: A case study, (Rollinger, C.; Horn, W., GWAI-86 und 2. Österreichische Artificial-Intelligence-Tagung, (1986), Springer Berlin), 69-74
[9] 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
[10] Kaczmarek, T. S.; Bates, R.; Robins, G., Recent developments in NIKL, (Proceedings AAAI-86, Philadelphia, PA, (1986)), 978-987
[11] Kanellakis, P. C.; Mitchell, J. C., Polymorphic unification and ML typing, (Proceedings 16th ACM Symposium on Principles of Programming Languages, (1989)), 5-15
[12] Kasper, R. T., A unification method for disjunctive feature descriptions, (Proceedings 25th Annual Meeting of the ACL, Stanford, CA, (1987)), 235-242
[13] Kobsa, A., The SB-ONE knowledge representation workbench, (Preprints Workshop on Formal Aspects of Semantic Networks, Two Harbors, CA, (1989))
[14] Levesque, H. J., Logic and the complexity of reasoning, J. Philos. Logic, 17, 355-389, (1988)
[15] Levesque, H. J.; Brachman, R. J., Expressiveness and tractability in knowledge representation and reasoning, Comput. Intell., 3, 78-93, (1987)
[16] Lipkis, T., A KL-ONE classifier, (Schmolze, J. G.; Brachman, R. J., Proceedings 1981 KL-ONE Workshop, Cambridge, MA, BBN Report No. 4842 and Fairchild Tech. Rept. No. 618, (1982)), 128-145
[17] McGregor, R.; Bates, R., The loom knowledge representation language, (Tech. Rept. ISI/RS-87-188, (1987), University of Southern California, Information Science Institute Marina del Rey, CA)
[18] Martelli, A.; Montanari, U., An efficient unification algorithm, ACM Trans. Program. Lang. Syst., 4, 258-282, (1982) · Zbl 0478.68093
[19] Nebel, B., Computational complexity of terminological reasoning in BACK, Artificial Intelligence, 34, 371-383, (1988) · Zbl 0646.68110
[20] Nebel, B., On terminological cycles, (Preprints Workshop on Formal Aspects of Semantic Networks, Two Harbors, CA (1989), KIT Rept., (1987), Department of Computer Science, Technische Universität Berlin), Preliminary version
[21] Nebel, B.; Smolka, G., Representation and reasoning with attributive descriptions, (Bläsius, K.; Hedtstück, U.; Rollinger, C., Sorts and Types in Artificial Intelligence, (1989), Springer Berlin) · Zbl 0747.68075
[22] Patel-Schneider, P. F., A four-valued semantics for terminological logics, Artifial Intelligence, 38, 319-351, (1989) · Zbl 0664.03024
[23] Patel-Schneider, P. F., Small can be beautiful in knowledge representation, (Proceedings IEEE Workshop on Principles of Knowledge-Based Systems, Denver, CO, (1984)), 11-16
[24] Patel-Schneider, P. F., Undecidability of subsumption in NIKL, Artificial Intelligence, 39, 263-272, (1989)
[25] Paterson, M. S.; Wegman, M. N., Linear unification, J. Comput. Syst. Sci., 16, 158-167, (1978) · Zbl 0371.68013
[26] Pigman, V., KRYPTON: description of an implementation, (AI Tech. Rept. 40, Vol. 1, (1984), Schlumberger Palo Alto Research Palo Alto, CA)
[27] Schild, K., Undecidability of \(U\), (KIT Rept. 67, (1988), Department of Computer Science, Technische Universität Berlin Berlin, FRG)
[28] Schmidt-Schauss, M., Subsumption in KL-ONE is undecidable, (Brachman, R. J.; Levesque, H. J.; Reiter, R., Proceedings First International Conference on Principles of Knowledge Representation and Reasoning, Toronto, Ont., (1989)), 421-431 · Zbl 0709.68096
[29] Schmidt-Schauss, M.; Smolka, G., Attributive concept descriptions with unions and complements, (IWBS Rept. 68, (1989), IBM Germany Scientific Center, IWBS Stuttgart, FRG), Artificial Intelligence (to appear)
[30] von Luck, K.; Nebel, B.; Peltason, C.; Schmiedel, A., The anatomy of the BACK system, (KIT Rept. 41, (1987), Department of Computer Science, Technische Universität Berlin Berlin, FRG)
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.