On the complexity of the instance checking problem in concept languages with existential quantification

Baader, F. & Hollunder, B. (1991). A Terminological Knowledge Representation System with Complete Inference Algorithm. InProc. Workshop on Processing Declarative Knowledge, PDK-19. Lecture Notes in Artificial Intelligence. Springer-Verlag: New York.

Brachman, R.J. & Levesque, H.J. (1984). The Tractability of Subsumption in Frame-Based Description Languages. InProc. 4th Nat. Conf. on Artificial Intelligence AAAI-84.

Donini, F.M., Hollunder, B., Lenzerini, M., Marchetti Spaccamela, A., Nardi, D. & Nutt, W.. (1992a). The Complexity of Existential Quantification in Concept Languages,Artificial Intelligence, 2?3, 309?327.

Donini, F.M., Lenzerini, M., Nardi, D. & Nutt, W. (1991). The Complexity of Concept Languages. In James Allen, Richard Fikes, and Erik Sandewall (Eds.),Proc. 2nd Int. Conf. on Principles of Knowledge Representation and Reasoning KR-91, pages 151?162, Morgan Kaufmann.

Donini, F.M., Lenzerini, M., Nardi, D., Nutt, W. & Schaerf, A. (1992b). Adding Epistemic Operators to Concept Languages. InProc. 3rd Int. Conf. On Principles of Knowledge Representation and Reasoning KR-92, pages 342?353.

Donini, F.M., Lenzerini, M., Nardi, D. & Schaerf, A. (1992c). From Subsumption to Instance Checking, Technical Report 15.92, Dipartimento di Informatica e Sistemistica, Universita di Roma ?La Sapienza.?

Garey, M.R. & Johnson, D.S. (1979).Computers and Intractability?A guide to NP-completeness, Freeman: San Francisco.

Lenzerini, M. & Schaerf, A. (1991a). Concept Languages as Query Languages. InProc. 9th Nat. Conf. on Artificial Intelligence AAAI-91.

Lenzerini, M. & Schaerf, A. (1991b). Querying Concept-Based Knowledge Bases. InProc. Workshop on Processing Declarative Knowledge, PDK-91, Lecture Notes in Artificial Intelligence. Springer-Verlag: New York.

Levesque, H.J. & Brachman, R.J. (1987). Expressiveness and Tractability in Knowledge Representation and Reasoning,Computational Intelligence, 3, 78?93.

MacGregor, R. (1991). Inside the LOOM Description Classifier,SIGART Bulletin, 2(3); 88?92.

Nebel, B. (1988). Computational Complexity of Terminological Reasoning in BAck,Artificial Intelligence, 34(3), 371?383.

Nebel, B. (1990a)Reasoning and Revision in Hybrid Representation Systems, Lecture Notes in Artificial Intelligence. Springer-Verlag: New York.

Nebel, B. (1990b). Terminological Reasoning is Inherently Intractable.Artificial Intelligence, 43, 235?249.

Nebel, B. (1991). Terminological Cycles: Semantics and Computational Properties. In John F. Sowa (ed.),Principles of Semantic Networks, pages 331?361. Morgan Kaufmann.

Patel-Schneider, P.F., McGuiness, D.L., Brachman, R.J., Alperin Resnick, L. & Borgida, A. (1991). The Classic Knowledge Representation System: Guiding Principles and Implementation Rationale.SIGART Bulletin, 2(3); 108?113.

Peltason, C. (1991). The BACK System-An Overview,SIGART Bulletin, 2(3); 114?119.

Schmidt-Schau?, M. (1989). Subsumption in KL-ONE Is Undecidable. In Ron J. Brachman, Hector J. Levesque, and Ray Reiter Ed,Proc. 1st Int. Conf. on Principles of Knowledge Representation and Reasoning KR-89. Morgan Kaufmann.

Schmidt-Schau?, M. & Smolka, G. (1991). Attributive Concept Descriptions with Complements,Artificial Intelligence, 48(1), 1?26.

Vardi, M. (1982). The Complexity of Relational Query Languages.In14th ACM Symp. on Theory of Computing, pages 137?146.