Is \( \mathcal{P}\mathcal{L}_2 \) a Tractable Language?

1. F. Baader. Augmenting concept languages by transitive closure of roles: An alternative to terminological cycles. In J. Mylopoulos and R. Reiter, editors, Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91), Sidney, Australia, pages 446–451. Morgan Kaufmann, 1991.

   Google Scholar 

2. F. Baader and B. Hollunder. A terminological knowledge representation system with complete inference algorithms. In H. Boley and M. M. Richter, editors, Proceedings of the International Workshop on Processing Declarative Knowledge (PDK’91), Kaiserslautern, Germany, volume 567 of Lecture Notes in Artificial Intelligence, pages 67–86. Springer-Verlag, 1991.

   Google Scholar 

3. R. J. Brachman and H. J. Levesque. The tractability of subsumption in frame-based description languages. In R. J. Brachman, editor, Proceedings of the 4th National Conference on Artificial Intelligence (AAAI-84), Austin, Texas, pages 34–37. AAAI Press / MIT Press, 1984.

   Google Scholar 

4. R. J. Brachman and J. G. Schmolze. An overview of the KL-ONE knowledge representation system. Cognitive Science, 9(2):171–216, 1985.

   Article  Google Scholar 

5. M. Buchheit, F. M. Donini, and A. Schaerf. Decidable reasoning in terminological knowledge representation systems. In R. Bajcsy, editor, Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93), Chambéry, France, pages 704–709. Morgan Kaufmann, 1993.

   Google Scholar 

6. F. M. Donini, M. Lenzerini, D. Nardi, B. Hollunder, W. Nutt, and A. M. Spaccamela. The complexity of existential quantification in concept languages. Artificial Intelligence, 53(2–3):309–327, 1992.

   Article  MathSciNet  Google Scholar 

7. F. M. Donini, M. Lenzerini, D. Nardi, and W. Nutt. The complexity of concept languages. In J. Allen, R. Fikes, and E. Sandewall, editors, Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning (KR’91), Cambridge, Massachusetts, pages 151–162. Morgan Kaufmann, 1991.

   Google Scholar 

8. F. M. Donini, M. Lenzerini, D. Nardi, and W. Nutt. Tractable concept languages. In J. Mylopoulos and R. Reiter, editors, Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91), Sidney, Australia, pages 458–463. Morgan Kaufmann, 1991.

   Google Scholar 

9. F. M. Donini, M. Lenzerini, D. Nardi, and A. Schaerf. Deduction in concept languages: from subsumption to instance checking. Journal of Logic and Computation, 4(4):423–452, 1994.

   Article  MATH  MathSciNet  Google Scholar 

10. B. Hollunder and W. Nutt. Subsumption algorithms for concept languages. Research Report RR-90-04, DFKI, Postfach 2080, D-6750 Kaiserslautern, Germany, 1990.

    Google Scholar 

11. T. S. Kaczmarek, R. Bates, and G. Robins. Recent developments in NIKL. In T. R. S. Kehler, editor, Proceedings of the 5th National Conference on Artificial Intelligence (AAAI-86), Philadelphia, Pennsylvania, pages 978–985. AAAI Press / MIT Press, 1986.

    Google Scholar 

12. M. Lenzerini and A. Schaerf. Concept languages as query languages. In T. Dean and K. McKeown, editors, Proceedings of the 9th National Conference on Artificial Intelligence (AAAI-91), Anaheim, California, pages 471–476. AAAI Press / MIT Press, 1991.

    Google Scholar 

13. H. J. Levesque and R. J. Brachman. A fundamental tradeoff in knowledge representation and reasoning (revised version). In R. J. Brachman and H. J. Levesque, editors, Readings in Knowledge Representation, pages 41–70. Morgan Kaufmann, 1985.

    Google Scholar 

14. M. Mamede and L. Monteiro. \( \mathcal{A}\mathcal{L}\mathcal{C} \)rn: A decidable terminological language with role negation. In C. Rowles, H. Liu, and N. Foo, editors, Proceedings of the 6th Australian Joint Conference on Artificial Intelligence (AI’93), Melbourne, Australia, pages 229–235. World Scientific Publishing, 1993.

    Google Scholar 

15. B. Nebel. Computational complexity of terminological reasoning in BACK. Artificial Intelligence, 34(3):371–383, 1988.

    Article  MATH  MathSciNet  Google Scholar 

16. B. Nebel. Reasoning and Revision in Hybrid Representation Systems, volume 422 of Lecture Notes in Artificial Intelligence. Springer-Verlag, 1990.

    Google Scholar 

17. B. Nebel. Terminological reasoning is inherently intractable. Artiticial Intelligence, 43(2):235–249, 1990.

    Article  MATH  MathSciNet  Google Scholar 

18. P. F. Patel-Schneider. Undecidability of subsumption in NIKL. Artificial Intelligence, 39(2):263–272, 1989.

    Article  MathSciNet  Google Scholar 

19. A. Schaerf. On the complexity of the instance checking problem in concept languages with existential quantification. In H. J. Komorowski and Z. W. Raś, editors, Proceedings of the 7th International Symposium on Methodologies for Intelligence Systems (ISMIS’93), Trondheim, Norway, volume 689 of Lecture Notes in Artificial Intelligence, pages 508–517. Springer-Verlag, 1993.

    Google Scholar 

20. K. Schild. Undecidability of subsumption in U. KIT Report 67, Technische Universität Berlin, Fachbereich Informatik, Franklinstr. 28/29, D-1000 Berlin 10, Germany, 1988.

    Google Scholar 

21. M. Schmidt-Schauß. Subsumption in KL-ONE is undecidable. In R. J. Brachman, H. J. Levesque, and R. Reiter, editors, Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR’89), Toronto, Ontario, pages 421–431. Morgan Kaufmann, 1989.

    Google Scholar 

22. M. Schmidt-Schauß and G. Smolka. Attributive concept descriptions with complements. Artificial Intelligence, 48(1):1–26, 1991.

    Article  MATH  MathSciNet  Google Scholar 

23. A. Vitória. Is \( \mathcal{P}\mathcal{L}_2 \) tractable? UPMAIL Technical Report 155, Uppsala University, Box 311, S-751 05 Uppsala, Sweden, 1998.

    Google Scholar 

Download references