×

zbMATH — the first resource for mathematics

Attributive concept descriptions with complements. (English) Zbl 0712.68095
Summary: We investigate the consequences of adding unions and complements to attributive concept descriptions employed in terminological knowledge representation languages. It is shown that deciding coherence and subsumption of such descriptions are PSPACE-complete problems that can be decided with linear space.

MSC:
68T30 Knowledge representation
68Q25 Analysis of algorithms and problem complexity
68T99 Artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aït-Kaci, H., An algebraic semantics approach to the effective resolution of type equations, Theor. comput. sci., 45, 293-351, (1986) · Zbl 0628.68010
[2] Aït-Kaci, H., A lattice-theoretic approach to computation based on a calculus of partially ordered type structures, ()
[3] Aït-Kaci, H.; Nasr, R., LOGIN: a logic programming language with built-in inheritance, J. logic program., 3, 185-215, (1986) · Zbl 0599.68013
[4] Borgida, A.; Brachman, R.J.; McGuiness, D.L.; Resnick, L.A., CLASSIC: a structural data model for objects, (), 59-67
[5] Brachman, R.J.; Levesque, H.J., The tractability of subsumption in frame-based description languages, (), 34-37
[6] Brachman, R.J.; Gilbert, V.Pigman; Levesque, H.J., An essential hybrid reasoning system: knowledge and symbol level accounts in KRYPTON, (), 532-539
[7] Brachman, R.J.; Schmolze, J.G., An overview of the KL-ONE knowledge representation system, Cogn. sci., 9, 2, 171-216, (1985)
[8] F. Donini, B. Hollunder, M. Lenzerini, A.M. Spaccamela, D. Nardi and W. Nutt, The complexity of existential quantification in terminological reasoning, DFKI-Rept., DFKI, Kaiserslautern, FRG (to appear). · Zbl 1193.68241
[9] Dörre, J.; Eisele, A., Determining consistency of feature terms with distributed disjunctions, (), 270-279
[10] Doyle, J.; Patil, R.S., Language restrictions, taxonomic classifications, and the utility of representation services, (), Artif. intell., (1991), also
[11] Eisele, A.; Dörre, J., Unification of disjunctive feature descriptions, (), 286-294
[12] Garey, M.R.; Johnson, D.S., ()
[13] Hollunder, B.; Nutt, W., Subsumption algorithms for concept description languages, ()
[14] Kaczmarek, T.S.; Bates, R.; Robins, G., Recent developments in NIKL, (), 978-987
[15] Kaplan, R.M.; Bresnan, J., Lexical-functional grammar: a formal system for grammatical representation, (), 173-381
[16] Kasper, R.T., Feature structures: a logical theory with applications to language analysis, ()
[17] Kasper, R.T., A unification method for disjunctive feature descriptions, (), 235-242
[18] Kasper, R.T.; Rounds, W.C., A logical semantics for feature structures, (), 257-265
[19] Kay, M., Functional grammar, ()
[20] Levesque, H.J.; Brachman, R.J., Expressiveness and tractability in knowledge representation and reasoning, Comput. intell., 3, 78-93, (1987)
[21] Levesque, H.J.; Brachman, R.J., A fundamental tradeoff in knowledge representation and reasoning (revised version), (), 41-70
[22] MacGregor, R.; Bates, R., The loom knowledge representation language, ()
[23] Nebel, B., Computational complexity of terminological reasoning in BACK, Artif. intell., 34, 371-383, (1988) · Zbl 0646.68110
[24] Nebel, B., Reasoning and revision in hybrid representation systems, (), also in: Lecture Notes in Artificial Intelligence (Springer, Berlin, to appear) · Zbl 0702.68095
[25] Nebel, B.; Nebel, B., Terminological reasoning is inherently intractable, (), Artif. intell., 43, 235-249, (1990), also · Zbl 0717.68089
[26] Nebel, B.; Smolka, G., Representation and reasoning with attributive descriptions, (), 112-139, also in · Zbl 0747.68075
[27] Nebel, B.; von Luck, K., Hybrid reasoning in BACK, (), 260-269
[28] Patel-Schneider, P.F., Small can be beautiful in knowledge representation, (), 11-16
[29] Pollard, C.; Sag, I.A., An information-based syntax and semantics, ()
[30] Rounds, W.C.; Kasper, R.T., A complete logical calculus for record structures representing linguistic information, (), 38-43
[31] Schmidt-Schauß, M., Subsumption in KL-ONE is undecidable, (), 421-431 · Zbl 0709.68096
[32] Shieber, S.M., An introduction to unification-based approaches to grammar, () · Zbl 0770.68008
[33] Smolka, G., Feature constraint logics for unification grammars, (), also J. Logic Program. (to appear) · Zbl 0754.68108
[34] Smolka, G., A feature logic with subsorts, ()
[35] 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.