Unification of concept terms in description logics. (English) Zbl 0970.68166

Summary: Unification of concept terms is a new kind of inference problem for description logics, which extends the equivalence problem by allowing one to replace certain concept names by concept terms before testing for equivalence. We show that this inference problem is of interest for applications, and present first decidability and complexity results for a small concept description language.


68T30 Knowledge representation
Full Text: DOI Link


[1] Aiken, A.; Kozen, D.; Vardi, M.; Wimmers, E., The complexity of set constraints, (), 1-17 · Zbl 0953.68557
[2] Baader, F., Unification in commutative theories, J. symb. comput., 8, 479-497, (1989) · Zbl 0689.68039
[3] Baader, F., Terminological cycles in KL-ONE-based knowledge representation languages, Proceedings of the eighth national conference on artificial intelligence, AAAI-90, Boston, U.S.A, (1990), p. 621-626
[4] Baader, F., Augmenting concept languages by transitive closure of roles: an alternative to terminological cycles, (), 446-451 · Zbl 0742.68064
[5] Baader, F., Unification in commutative theories, hilbert’s basis theorem and Gröbner bases, J. ACM, 40, 477-503, (1993) · Zbl 0791.68146
[6] Baader, F.; Buchheit, M.; Hollunder, B., Cardinality restrictions on concepts, Artifi. intell., 88, 195-213, (1996) · Zbl 0907.68181
[7] Baader, F.; Hanschke, P., A scheme for integrating concrete domains into concept languages, (), 452-457 · Zbl 0742.68063
[8] Baader, F.; Hollunder, B., A terminological knowledge representation system with complete inference algorithms, (), 67-85
[9] Baader, F.; Küsters, R.; Borgida, A.; McGuinness, D., Matching in description logics, J. logic comput., 9, 411-447, (1999) · Zbl 0940.03036
[10] Baader, F.; Narendran, P., Unification of concept terms in description logics, (), 331-335
[11] Baader, F.; Nutt, W., Combination problems for commutative/monoidal theories: how algebra can help in equational reasoning, J. applicable algebra eng. commun. comput., 7, 309-337, (1996) · Zbl 0853.03008
[12] Baader, F.; Sattler, U., Description logics with symbolic number restrictions, (), 283-287
[13] Baader, F.; Sattler, U., Knowledge representation in process engineering, Proceedings of the international workshop on description logics, Cambridge (Boston), MA, (1996), AAAI Press/The MIT Press U.S.A
[14] Baader, F.; Sattler, U., Number restrictions on complex roles in description logics, (), 328-339
[15] Baader, F.; Siekmann, J., Unification theory, ()
[16] Bergamaschi, S.; Beneventano, D., Incoherence and subsumption for recursive views and queries in object-oriented data models, Data knowl. eng., 21, 217-252, (1997) · Zbl 0900.68169
[17] Bergamaschi, S.; Sartori, C.; Beneventano, D.; Vincini, M., ODB-tools: a description logics based tool for schema validation and semantic query optimization in object oriented databases, (), 435-438
[18] Borgida, A.; McGuinness, D., Asking queries about frames, Proceedings of the fifth international conference on principles of knowledge representation and reasoning, KR’96, Cambridge, MA, U.S.A, (1996), p. 340-349
[19] Borgida, A.; Patel-Schneider, P., A semantics and complete algorithm for subsumption in the CLASSIC description logic, J. artifi. intell. res., 1, 277-308, (1994) · Zbl 0900.68397
[20] Brachman, R.J.; McGuinness, D.L.; Patel-Schneider, P.F.; Resnick, L.A.; Borgida, A., Living with CLASSIC: when and how to use a KL-ONE-like language, (), 401-456
[21] Brachman, R.J.; Schmolze, J.G., An overview of the KL-ONE knowledge representation system, Cogn. sci., 9, 171-216, (1985)
[22] Buchheit, M.; Donini, F.M.; Schaerf, A., Decidable reasoning in terminological knowledge representation systems, J. artifi. intell. res., 1, 109-138, (1993) · Zbl 0900.68396
[23] Buchheit, M.; Jeusfeld, M.; Nutt, W.; Staudt, M., Subsumption of queries to object-oriented databases, Information systems, 19, 33-54, (1994)
[24] Buchheit, M.; Klein, R.; Nutt, W., Configuration as model construction: the constructive problem solving approach, Proceedings of the third international conference on artificial intelligence in design, AID’94, Lausanne, Switzerland, (1994)
[25] Bürckert, H.-J., Matching—a special case of unification?, J. symb. comput., 8, 532-536, (1989) · Zbl 0691.03004
[26] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi
[27] Devanbu, P.; Brachman, R.J.; Selfridge, P.G.; Ballard, B.W., Lassie: a knowledge-based software information system, Communications of the ACM, 34, 34-49, (1991)
[28] Donini, F.M.; Hollunder, B.; Lenzerini, M.; Spaccamela, A.M.; Nardi, D.; Nutt, W., The complexity of existential quantification in concept languages, J. artifi. intell., 53, 309-327, (1992) · Zbl 1193.68241
[29] Donini, F.M.; Lenzerini, M.; Nardi, D.; Nutt, W., The complexity of concept languages, (), 151-162 · Zbl 0765.68187
[30] Donini, F.M.; Lenzerini, M.; Nardi, D.; Nutt, W., Tractable concept languages, (), 458-463 · Zbl 0742.68066
[31] Donini, F.M.; Lenzerini, M.; Nardi, D.; Schaerf, A., Deduction in concept languages: from subsumption to instance checking, J. logic. comput., 4, 423-452, (1994) · Zbl 0809.68109
[32] Garey, M.; Johnson, D., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman and Company New York · Zbl 0411.68039
[33] Gécseg, F.; Steinby, M., Tree automata, (1984), Akadémiai Kiaddá Hungary, Budapest
[34] Gilleron, R.; Tison, S.; Tommassi, M., Some new decidability results on positive and negative set constraints, (), 336-351
[35] Hollunder, B.; Baader, F., Qualifying number restrictions in concept languages, (), 335-346 · Zbl 0765.68190
[36] Hollunder, B.; Nutt, W.; Schmidt-Schauß, M., Subsumption algorithms for concept description languages, (), 348-353
[37] Koehler, J., An application of terminological logics to case-based reasoning, (), 351-362
[38] Levesque, H.J.; Brachman, R.J., Expressiveness and tractability in knowledge representation and reasoning, Comput. intell., 3, 78-93, (1987)
[39] McGuinness, D.L.; Resnick, L.A.; Isbell, C., Description logic in practice: a classic application, Proceedings of the 14th international joint conference on artificial intelligence, IJCAI’95, montréal, Canada, (1995), Morgan Kaufmann, Video Presentation San Francisco, p. 2045-2046
[40] Narendran, P., Solving linear equations over polynomial semirings, 11th annual symposium on logic in computer science, LICS’96, (1996), Rutger University (NJ), IEEE Computer Society Press, p. 466-472
[41] Nebel, B., Computational complexity of terminological reasoning in BACK, J. artifi. intell., 34, 371-383, (1988) · Zbl 0646.68110
[42] Nebel, B., Reasoning and revision in hybrid representation systems, (1990), Springer-Verlag · Zbl 0702.68095
[43] Nebel, B., Terminological reasoning is inherently intractable, J. artifi. intell., 43, 235-249, (1990) · Zbl 0717.68089
[44] Nutt, W., Unification in monoidal theories, (), 618-632
[45] Quantz, J.; Schmitz, B., Knowledge-based disambiguation for machine translation, Minds Mach., 4, 39-57, (1994)
[46] Rychtyckyj, N., DLMS: an evaluation of KL-ONE in the automobile industry, (), 588-596
[47] Schaerf, A., On the complexity of the instance checking problem in concept languages with existential quantification, J. intell. inf. syst., 2, 265-278, (1993)
[48] Schmidt-Schauß, M.; Smolka, G., Attributive concept descriptions with complements, J. artifi. intell., 47, 1-26, (1991) · Zbl 0712.68095
[49] Seidl, H., Haskell overloading is DEXPTIME-complete, Inf. process. lett., 52, 57-60, (1994) · Zbl 0835.68008
[50] Thomas, W., Automata on infinite objects, (), 133-191 · Zbl 0900.68316
[51] Woods, W.A.; Schmolze, J.G., The KL-ONE family, Comput. math. appl., 23, 133-177, (1992) · Zbl 0800.68874
[52] Wright, J.R.; Weixelbaum, E.S.; Brown, K.; Vesonder, G.T.; Palmer, S.R.; Berman, J.I.; Moore, H.H., A knowledge-based configurator that supports sales, engineering, and manufacturing at AT&T network systems, AI mag., 14, 69-80, (1993)
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.