$$\boldsymbol{\mathcal{ALCQPI}}_{\boldsymbol{R}^{\mathbf{+}}}$$ : Rational Grading in an Expressive Description Logic with Inverse and Transitive Roles and Counting
Tóm tắt
In this paper, we consider the expressive Description Logic (DL)
$$\mathcal{ALCQPI}_{R^{+}}$$
having concept constructors called part
restrictions that realize rational grading. Part restrictions are
able to convey statements about a rational part of a set of
successors, and they essentially enrich the expressive
capabilities of DLs. That is why it is important to evaluate the
cost of their use with respect to the reasoning complexity. We
modify the tableaux algorithm used for
$$\mathcal{ALCNI}_{R^{+}}$$
(a
DL with just number restrictions instead of qualified number
ones), and augment it with a specific technique for dealing with
part restrictions to prove that concept satisfiability and
subsumption in the considered DL are still in PSPACE.
Tài liệu tham khảo
W. J. Savitch, ‘‘Relationship between nondeterministic and deterministic tape complexities’’, J. Comput. Syst. Sci. 4, 177–192 (1970).
K. Fine, ‘‘In so many possible worlds’’, Notre Dame J. Formal Logic 13, 516–520 (1972).
M. Schmidt-Schauß and G. Smolka, ‘‘Attributive concept descriptions with complements’’, Artif. Intell. 48 (1), 1–26 (1991).
U. Sattler, ‘‘A concept language extended with different kinds of transitive roles’’, in 20th Deutsche Jahrestagung für Künstliche Intelligenz, Ed. by G. Görz and S. Hölldobler, Vol. 1137 of Lecture Notes in Artificial Intelligence (Springer, Berlin, 1996).
F. M. Donini, M. Lenzerini, D. Nardi, and W. Nutt, ‘‘The complexity of concept languages’’, Inform. Comput.134, 1–58 (1997).
I. Horrocks, U. Sattler, and S. Tobies, ‘‘A PSpace-algorithm for deciding \(\mathcal{ALCNI}_{R^{+}}\)-satisfiability’’, LTCS-Report 98-08 (LuFG Theor. Comput. Sci., RWTH Aachen, Germany, 1998).
I. Horrocks, U. Sattler, and S. Tobies, ‘‘Practical reasoning for expressive description logics’’, inProceedings of the 6th International Conference on Logic Programming and Automated Reasoning, LPAR ’99 (Springer, Berlin, 1999), pp. 161–180.
S. Tobies, ‘‘A PSpace algorithm for graded modal logic’’, in Automated Deduction—CADE-16, Lect. Notes Comput. Sci. 1632, 52–66 (1999).
V. Haarslev, M. Timmann, and R. Möller, ‘‘Combining tableaux and algebraic methods for reasoning with qualified number restrictions’’, in Proceedings of the DL 2001, CEUR Workshop Proceedings (2001), Vol. 49. CEUR-wS.org.
E. Pacuit and S. Salame, ‘‘Majority logic’’, inProceedings of the Conference on Principles of Knowledge Representation and Reasoning KR 2004 (2004), pp. 598–605.
T. Tinchev and M. Yanchev, ‘‘Modal operators for rational grading’’, in Proceedings of the International Conference on Pioneers of Bulgarian Mathematics, Sofia, Bulgaria, 2006, pp. 123–124.
S. Demri and D. Lugiez, ‘‘Presburger modal logic is PSPACE-complete’’, in Proceedings of the International Conference on Automated Reasoning IJCAR 2006, Lect. Notes Comput. Sci. 4130 (2006).
T. Lai, J. Endrullis, and L. S. Moss, ‘‘Majority digraphs’’, arXiv: 1509.07567 (2015).
F. Baader, ‘‘A new description logic with set constraints and cardinality constraints on role successors’’, inProceedings of the Conference FroCoS, 2017, pp. 43–59.
M. Yanchev, ‘‘Part restrictions: Adding new expressiveness in description logics’’, in Abstracts of Informal Presentations CiE 2012 (2012), p. 144.
M. Yanchev, ‘‘Part restrictions in description logics: Reasoning in polynomial time complexity’’, inProceedings of the LC 2012 Conference (2012), pp. 38–39.
M. Yanchev, ‘‘Part restrictions in description logics with union and counting constructors’’, inProceedings of the Conference CiE 2013 (2013), p. 43.
M. Yanchev, ‘‘PSPACE rational grading with inverse relations and intersection of relations’’, inProceedings of the International Conference on Algebra and Mathematical Logic: Theory and Applications, Kazan, Russia, 2014, p. 168.
M. Yanchev, ‘‘A description logic with part restrictions: PSPACE-complete expressiveness’’, inProceedings of the Conference CiE 2014, Budapest, Hungary, 2014, Ed. by A. Beckmann, E. Csuhaj-Varjú, and K. Meer, pp. 261–270.
M. Yanchev, ‘‘Rational grading in an expressive description logic’’, in Proceedings of the 32nd International Workshop on Description Logic, DL 2019, Ed. by M. Šimkus and G. Weddell (2019).