Horn Knowledge Bases in Regular Description Logics with PTIME Data Complexity

• Autorzy: Nguyen L.A. L.A.
• Języki publikacji: EN

Abstrakty

EN

Developing a good formalism and an efficient decision procedure for the instance checking problem is desirable for practical application of description logics. The data complexity of the instance checking problem is coNP-complete even for Horn knowledge bases in the basic descriptionn logic ALC. In this paper, we present and study weakenings with PTIME data complexity of the instance checking problem for Horn knowledge bases in regular description logics. We also study cases when the weakenings are an exact approximation. In contrast to previous related work of other authors, our approach deals with the case when the constructor ∀ is allowed in premises of program clauses that are used as terminological axioms.

Słowa kluczowe

EN

Horn knowledge bases; description logics; regular grammar logics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 4
• Strony: 349--384
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Nguyen L.A. L.A.

• Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland,

Bibliografia

• [1] Baader, F., Brandt, S., Lutz, C.: Pushing the EL Envelope, Proceedings of IJCAI'2005 (L. Kaelbling, A. Saffiotti, Eds.), Morgan-Kaufmann Publishers, 2005.
• [2] Baader, F., Sattler, U.: An Overview of Tableau Algorithms for Description Logics, Studia Logica, 69, 2001, 5-40.
• [3] Baldoni, M., Giordano, L., Martelli, A.: A Tableau for Multimodal Logics and Some (Un)Decidability Results, Proceedings of TABLEAUX'1998, LNCS 1397 (H. de Swart, Ed.), 1998.
• [4] Brandt, S.: Polynomial Time Reasoning in a Description Logic with Existential Restrictions, GCI Axioms, and - What Else?, Proceedings of ECAI'2004 (R. de M´antaras, L. Saitta, Eds.), IOS Press, 2004.
• [5] Calvanese, D., Giacomo, G. D., Lembo, D., Lenzerini, M., Rosati, R.: Tractable Reasoning and Efficient Query Answering in Description Logics: The L-Lite Family, J. Autom. Reasoning, 39(3), 2007, 385-429.
• [6] Calvanese, D., Giacomo, G. D., Lenzerini, M., Nardi, D.: Reasoning in Expressive Description Logics, in: Handbook of Automated Reasoning (A. Robinson, A. Voronkov, Eds.), Elsevier, 2001, 1581-1634.
• [7] Debart, F., Enjalbert, P., Lescot, M.: Multimodal Logic Programming Using Equational and Order-Sorted Logic, Theoretical Comp. Science, 105, 1992, 141-166.
• [8] Demri, S.: The Complexity of Regularity in Grammar Logics and Related Modal Logics, Journal of Logic and Computation, 11(6), 2001, 933-960.
• [9] Demri, S., de Nivelle, H.: Deciding Regular Grammar Logics with Converse Through First-Order Logic, Journal of Logic, Language and Information, 14(3), 2005, 289-329.
• [10] Dunin-Ke¸plicz, B., Nguyen, L., Szałas, A.: Fusing Approximate Knowledge from Distributed Sources, Proceedings of IDC'2009 (G. Papadopoulos, C. Badica, Eds.), 237, Springer, 2009.
• [11] Dunin-Ke¸plicz, B., Nguyen, L., Szałas, A.: Tractable approximate knowledge fusion using the Horn fragment of serial propositional dynamic logic, Int. J. Approx. Reasoning, 51(3), 2010, 346-362.
• [12] Fischer, M., Ladner, R.: Propositional Dynamic Logic of Regular Programs, J. Comput. Syst. Sci., 18(2), 1979, 194-211.
• [13] Goré, R., Nguyen, L.: A Tableau System with Automaton-Labelled Formulae for Regular Grammar Logics, Proceedings of TABLEAUX 2005, LNAI 3702 (B. Beckert, Ed.), Springer-Verlag, 2005.
• [14] Grosof, B., Horrocks, I., Volz, R., Decker, S.: Description logic programs: combining logic programs with description logic, WWW, 2003.
• [15] Harel, D., Kozen, D., Tiuryn, J.: Dynamic Logic, MIT Press, 2000.
• [16] Horrocks, I., Kutz, O., Sattler, U.: The Even More Irresistible SROIQ, Proceedings of KR'2006 (P. Doherty, J. Mylopoulos, C. Welty, Eds.), AAAI Press, 2006.
• [17] Horrocks, I., Sattler, U.: Decidability of SHIQ with complex role inclusion axioms, Artificial Intelligence, 160(1-2), 2004, 79-104.
• [18] Hustadt, U., Motik, B., Sattler, U.: Reasoning in Description Logics by a Reduction to Disjunctive Datalog, J. Autom. Reasoning, 39(3), 2007, 351-384.
• [19] Krisnadhi, A., Lutz, C.: Data Complexity in the EL Family of Description Logics, Proceedings of LPAR'2007, LNCS 4790 (N. Dershowitz, A. Voronkov, Eds.), Springer, 2007.
• [20] Krötzsch, M., Rudolph, S., Hitzler, P.: Complexity Boundaries for Horn Description Logics, Proceedings of AAAI'2007, AAAI Press, 2007.
• [21] Krötzsch, M., Rudolph, S., Hitzler, P.: Conjunctive Queries for a Tractable Fragment of OWL 1.1, Proceedings of ISWC'2007 + ASWC'2007, LNCS 4825, Springer, 2007.
• [22] Mateescu, A., Salomaa, A.: Formal Languages: an Introduction and a Synopsis, in: Handbook of Formal Languages - Volume 1: Word, Language, Grammar (G. Rozenberg, A. Salomaa, Eds.), Springer, 1997, 1-40.
• [23] Nguyen, L.: Constructing the Least Models for Positive Modal Logic Programs, Fundamenta Informaticae, 42(1), 2000, 29-60.
• [24] Nguyen, L.: On the Complexity of Fragments of Modal Logics, Advances in Modal Logic - Volume 5 (R. A. Schmidt, I. Pratt-Hartmann, M. Reynolds, H. Wansing, Eds.), King's College Publications, 2004.
• [25] Nguyen, L.: A Bottom-up Method for the Deterministic Horn Fragment of the Description Logic ALC, Proceedings of JELIA 2006, LNAI 4160 (M. Fisher, W. van der Hoek, B. Konev, A. Lisitsa, Eds.), Springer-Verlag, 2006.
• [26] Nguyen, L.: On the Deterministic Horn Fragment of Test-free PDL, Advances in Modal Logic - Volume 6 (I. Hodkinson, Y. Venema, Eds.), King's College Publications, 2006.
• [27] Nguyen, L.: Approximating Horn Knowledge Bases in Regular Description Logics to Have PTIME Data Complexity, Proceedings of ICLP'2007, LNCS 4670 (V. Dahl, I. Niemel¨a, Eds.), Springer, 2007.
• [28] Nguyen, L.: Weakening Horn Knowledge Bases in Regular Description Logics to Have PTIME Data Complexity, Proceedings of Automated Deduction: Decidability, Complexity, Tractability ADDCT'07 (S. Ghilardi, U. Sattler, V. Sofronie-Stokkermans, A. Tiwari, Eds.), 2007.
• [29] Nguyen, L.: Constructing Finite Least Kripke Models for Positive Logic Programs in Serial Regular Grammar Logics, Logic Journal of the IGPL, 16(2), 2008, 175-193.
• [30] Nguyen, L.: The long version of this paper, Available at http://www.mimuw.edu.pl/~nguyen/RG.pdf, 2010.
• [31] Nonnengart, A.: How to Use Modalities and Sorts in Prolog, Proceedings of JELIA'94, LNCS 838 (C. Mac-Nish, D. Pearce, L. Pereira, Eds.), Springer, 1994.
• [32] Pratt, V.: Models of Program Logics, Proceedings of FOCS'1979, IEEE, 1979.
• [33] Rosati, R.: On Conjunctive Query Answering in EL, Proceedings of DL'2007.
• [34] Schild, K.: Terminological Cycles and the Propositional _-Calculus, Proceedings of KR'1994, 1994.