×

Satisfiability and reasoning mechanism of terminological cycles in description logic \(v\mathcal L\). (English) Zbl 1149.68426

Summary: The current research works and the existing problems of terminological cycles in description logics are analyzed in this paper. Referring to the works of F. Baader and B. Nebel, we aim at a new direction. First, the description logic \(v\mathcal{L}\) is defined, and the description graphs GT and GJ are redefined. A syntax condition for the satisfiability of the membership relation is given. By using this syntax condition, we prove the following: The subsumption reasoning in \(v\mathcal{L}\) with respect to the gfp-model, the lfp-model and the descriptive model is polynomial.

MSC:

68T27 Logic in artificial intelligence

Software:

Pellet; Racer; FaCT++
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Giacomo G D, Lenzerini M. A uniform framework for concept definitions in description logics. J Art Intell Res, 1997, 6(1): 87–110 · Zbl 0894.68095
[2] Buchheit M, Donini F M, Nutt W, et al. A refined architecture for terminological systems: terminology = schema + views. Art Intell, 1998, 99(2): 209–260 · Zbl 0896.68132 · doi:10.1016/S0004-3702(97)00079-9
[3] Sirin E, Parsia B, Grau B C, et al. Pellet: a practical OWL-DL reasoner. J Web Semantics: Science, Services and Agents on the World Wide Web, 2007, 5(2): 51–53 · Zbl 05461213 · doi:10.1016/j.websem.2007.03.004
[4] Tsarkov D, Horrocks I. FaCT++ description logic reasoner: system description. In: Furbach U, Shankar N, eds. Proceedings of the 3rd International Joint Conference on Automated Reasoning (IJCAR 2006). LNAI 4130. Berlin: Springer, 2006. 292–297
[5] Haarslev V, Moller R. RACER system description. In: Haarslev V, Moller R, eds. Proceedings of the 1st International Joint Conference on Automated Reasoning (IJCAR 2001). LNAI 2083. London: Springer, 2001. 701–706 · Zbl 0988.68599
[6] Shi Z Z, Dong M K, Jiang Y C, et al. A logic foundation for the semantic Web. Sci China Ser F-Inf Sci, 2005, 48(2): 161–178 · doi:10.1360/03yf0506
[7] Baader F. Using automata theory for characterizing the semantics of terminological cycles. Ann Math Art Intell, 1996, 18(2–4): 175–219 · Zbl 0891.68111 · doi:10.1007/BF02127747
[8] Nebel B. Terminological cycles: semantics and computational properties. In: Sowa J F, ed. Principles of Semantic Networks. San Francisco: Morgan Kaufmann Publishers, 1991. 331–362
[9] Nebel B. Reasoning and revision in hybrid representation systems. LNAI 422. Berlin: Springer-Verlag, 1990. 125–156
[10] Baader F. Terminological cycles in a description logic with existential restrictions. In: Gottlob G, Walsh T, eds. Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI 2003). San Francisco: Morgan Kaufmann Publishers, 2003. 325–330
[11] Henzinger M R, Henzinger T A, Kopke P W. Computing simulations on finite and infinite graphs. In: Prabhakar R, ed. Proceedings of the 36th Annual Symposium on Foundations of Computer Science. New York: IEEE Computer Society Press, 1995. 453–462 · Zbl 0938.68538
[12] Baader F, Calvanese D, McGuinness D, et al. The Description Logic Handbook: Theory, Implementation and Applications. Cambridge: Cambridge University Press, 2003. 47–141 · Zbl 1058.68107
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.