A Tractable Rule Language in the Modal and Description Logic that Combines CPDL with Regular Grammar Logic

• Autorzy: Nguyen L. A.

Identyfikatory

DOI

10.3233/FI-2016-1307

• Języki publikacji: EN

Abstrakty

EN

Combining CPDL (Propositional Dynamic Logic with Converse) and regular grammar logic results in an expressive modal logic denoted by CPDL_reg. This logic covers TEAMLOG, a logical formalism used to express properties of agents’ cooperation in terms of beliefs, goals and intentions. It can also be used as a description logic for expressing terminological knowledge, in which both regular role inclusion axioms and CPDL-like role constructors are allowed. In this paper, we develop an expressive and tractable rule language called Horn-CPDL_reg. As a special property, this rule language allows the concept constructor “universal restriction” to appear on the left hand side of general concept inclusion axioms. We use a special semantics for Horn-CPDL_reg that is based on pseudo-interpretations. It is called the constructive semantics and coincides with the traditional semantics when the concept constructor “universal restriction” is disallowed on the left hand side of concept inclusion axioms or when the language is used as an epistemic formalism and the accessibility relations are serial. We provide an algorithm with PTIME data complexity for checking whether a knowledge base in Horn-CPDL_reg has a pseudo-model. This shows that the instance checking problem in Horn-CPDL_reg with respect to the constructive semantics has PTIME data complexity.

Słowa kluczowe

EN

description logics; modality; axioms; data analysis; epistemic logic

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 143, nr 1/2
• Strony: 113--139
• Opis fizyczny: Bibliogr. 26 poz., rys., tab.

Twórcy

autor

Nguyen L. A.

• Division of Knowledge and System Engineering for ICT, Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City, Vietnam
• Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland

Bibliografia

• [1] Harel D, Kozen D, Tiuryn J. Dynamic Logic. MIT Press; 2000.
• [2] Demri S. The Complexity of Regularity in Grammar Logics and Related Modal Logics. Journal of Logic and Computation. 2001;11(6):933–960.
• [3] Demri S, de Nivelle H. Deciding Regular Grammar Logics with Converse Through First-Order Logic. Journal of Logic, Language and Information. 2005;14(3):289–329.
• [4] Dunin-Kęplicz B, Nguyen LA, Szałas A. Converse-PDL with Regular Inclusion Axioms: A Framework for MAS Logics. J Applied Non-Classical Logics. 2011;21(1):61–91.
• [5] Dunin-Kęplicz B, Verbrugge R. Collective Intentions. Fundam Inform. 2002;51(3):271–295.
• [6] Dziubiński M, Verbrugge R, Dunin-Kęplicz B. Complexity Issues in Multiagent Logics. Fundam Inform. 2007;75(1-4):239–262.
• [7] Nguyen LA. Horn Knowledge Bases in Regular Description Logics with PTime Data Complexity. Fundamenta Informaticae. 2010;104(4):349–384.
• [8] Grosof BN, Horrocks I, Volz R, Decker S. Description logic programs: combining logic programs with description logic. In: Proceedings of WWW’2003; 2003. p. 48–57.
• [9] Baader F, Brandt S, Lutz C. Pushing the EL Envelope. In: Proceedings of IJCAI’2005. Morgan-Kaufmann Publishers; 2005. p. 364–369.
• [10] Baader F, Brandt S, Lutz C. Pushing the EL Envelope Further. In: Proceedings of the OWLED 2008 DC Workshop on OWL: Experiences and Directions; 2008. .
• [11] Hustadt U, Motik B, Sattler U. Reasoning in Description Logics by a Reduction to Disjunctive Datalog. J Autom Reasoning. 2007;39(3):351–384.
• [12] Krisnadhi A, Lutz C. Data Complexity in the EL Family of Description Logics. In: Proceedings of LPAR’2007. vol. 4790 of LNCS. Springer; 2007. p. 333–347.
• [13] Krötzsch M, Rudolph S, Hitzler P. Conjunctive Queries for a Tractable Fragment of OWL 1.1. In: Proceedings of ISWC’2007 + ASWC’2007, LNCS 4825. Springer; 2007. p. 310–323.
• [14] Rosati R. On Conjunctive Query Answering in EL. In: Proceedings of DL’2007;. p. 451–458.
• [15] Ortiz M, Rudolph S, Simkus M. Query Answering in the Horn Fragments of the Description Logics SHOIQ and SROIQ. In: Proceedings of IJCAI 2011; 2011. p. 1039–1044.
• [16] Calvanese D, De Giacomo G, Lembo D, Lenzerini M, Rosati R. Data complexity of query answering in description logics. Artif Intell. 2013;195:335–360.
• [17] Calvanese D, Giacomo GD, Lembo D, Lenzerini M, Rosati R. Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. J Autom Reasoning. 2007;39(3):385–429.
• [18] Krötzsch M, Rudolph S, Hitzler P. Complexity Boundaries for Horn Description Logics. In: Proceedings of AAAI’2007. AAAI Press; 2007. p. 452–457.
• [19] Brandt S. Polynomial Time Reasoning in a Description Logic with Existential Restrictions, GCI Axioms, and - What Else? In: Proceedings of ECAI’2004. IOS Press; 2004. p. 298–302.
• [20] Nguyen LA. Constructing Finite Least Kripke Models for Positive Logic Programs in Serial Regular Grammar Logics. Logic Journal of the IGPL. 2008;16(2):175–193.
• [21] Dunin-Kęplicz B, Nguyen LA, Szałas A. Tractable Approximate Knowledge Fusion Using the Horn Fragment of Serial Propositional Dynamic Logic. Int J Approx Reasoning. 2010;51(3):346–362.
• [22] Dunin-Kęplicz B, Nguyen LA, Szałas A. Horn-TeamLog: A Horn Fragment of TeamLog with PTime Data Complexity. In: Proceedings of ICCCI’2013. vol. 8083 of LNCS. Springer; 2013. p. 143–153.
• [23] Nguyen LA. On the Deterministic Horn Fragment of Test-free PDL. In: Hodkinson I, Venema Y, editors. Advances in Modal Logic - Volume 6. King’s College Publications; 2006. p. 373–392.
• [24] Nguyen LA. A Bottom-up Method for the Deterministic Horn Fragment of the Description Logic ALC. In: Proceedings of JELIA’2006. vol. 4160 of LNAI. Springer-Verlag; 2006. p. 346–358.
• [25] Nguyen LA, Nguyen TBL, Szałas A. Towards richer rule languages with polynomial data complexity for the Semantic Web. Data Knowl Eng. 2015;96:57–77.
• [26] Horrocks I, Kutz O, Sattler U. The Even More Irresistible SROIQ. In: Proceedings of KR’2006. AAAI Press; 2006. p. 57–67.