Abstract
We investigate the temporal extension of the description logic \({\textsl{DL-Lite}_\textit{bool}^{\scriptscriptstyle(\mathcal{RN})}}\) with the until operator on concepts, rigid (time-independent) and local (time-dependent) roles, and rigid TBox axioms. Using an embedding into the one-variable fragment of first-order temporal logic and the quasimodel technique, we prove that (i) the satisfiability problem for the resulting logic is PSpace-complete, and that (ii) by weakening until to sometime in the future we obtain an NP-complete logic, which matches the complexities of the propositional linear-time temporal logics with the corresponding temporal operators.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: DL-Lite in the light of first-order logic. In: Proc. of the 22nd AAAI Conf. on Artificial Intelligence, pp. 361–366. AAAI Press, Menlo Park (2007)
Artale, A., Calvanese, D., Kontchakov, R., Zakharyaschev, M.: The DL-Lite family and relations. Technical Report BBKCS-09-03, School of Computer Science and Information Systems, Birbeck College, London (2009), http://www.dcs.bbk.ac.uk/research/techreps/2009/bbkcs-09-03.pdf
Artale, A., Franconi, E.: Temporal description logics. In: Fisher, M., Gabbay, D., Vila, L. (eds.) Handbook of Time and Temporal Reasoning in Artificial Intelligence, pp. 375–388. Elsevier, Amsterdam (2005)
Artale, A., Franconi, E., Wolter, F., Zakharyaschev, M.: A temporal description logic for reasoning about conceptual schemas and queries. In: Flesca, S., Greco, S., Leone, N., Ianni, G. (eds.) JELIA 2002. LNCS (LNAI), vol. 2424, pp. 98–110. Springer, Heidelberg (2002)
Artale, A., Parent, C., Spaccapietra, S.: Evolving objects in temporal information systems. Annals of Mathematics and AI 50(1-2), 5–38 (2007)
Artale, A., Calvanese, D., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M.: Reasoning over extended ER models. In: Parent, C., Schewe, K.-D., Storey, V.C., Thalheim, B. (eds.) ER 2007. LNCS, vol. 4801, pp. 277–292. Springer, Heidelberg (2007)
Artale, A., Kontchakov, R., Lutz, C., Wolter, F., Zakharyaschev, M.: Temporalising tractable description logics. In: Proc. of the 14th Int. Symposium on Temporal Representation and Reasoning (TIME). IEEE Computer Society, Los Alamitos (2007)
Artale, A., Lutz, C., Toman, D.: A description logic of change. In: Proc. of Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 218–223 (2007)
Baader, F., Küsters, R., Wolter, F.: Extensions to description logics. In: Description Logic Handbook, pp. 219–261. Cambridge University Press, Cambridge (2003)
Baader, F., Ghilardi, S., Lutz, C.: LTL over description logic axioms. In: Proc. of the 11th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp. 684–694. AAAI Press, Menlo Park (2008)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: DL-Lite: Tractable description logics for ontologies. In: Proc. of the 10th Nat. Conf. on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conf., pp. 602–607. AAAI Press/The MIT Press (2005)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Data complexity of query answering in description logics. In: Proc. of the 10th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp. 260–270. AAAI Press, Menlo Park (2006)
Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. J. of Automated Reasoning 39(3), 385–429 (2007)
Gabbay, D., Hodkinson, I., Reynolds, M.: Temporal Logic: Mathematical Foundations and Computational Aspects, vol. 1. Oxford University Press, Oxford (1994)
Gabbay, D., Kurucz, A., Wolter, F., Zakharyaschev, M.: Many-Dimensional Modal Logics: Theory and Applications. Elsevier, Amsterdam (2003)
Hall, G., Gupta, R.: Modeling transition. In: Proc. of the 7th Int. Conf. on Data Engineering (ICDE), pp. 540–549. IEEE Computer Society, Los Alamitos (1991)
Lutz, C., Wolter, F., Zakharyaschev, M.: Temporal description logics: A survey. In: Proc. of the 14th Int. Symposium on Temporal Representation and Reasoning (TIME), pp. 3–14. IEEE Computer Society, Los Alamitos (2008)
Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Linking data to ontologies. J. on Data Semantics X, 133–173 (2008)
Schild, K.: Combining terminological logics with tense logic. In: Damas, L.M.M., Filgueiras, M. (eds.) EPIA 1993. LNCS, vol. 727, pp. 105–120. Springer, Heidelberg (1993)
Spaccapietra, S., Parent, C., Zimanyi, E.: Conceptual Modeling for Traditional and Spatio-Temporal Applications—The MADS Approach. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Artale, A., Kontchakov, R., Ryzhikov, V., Zakharyaschev, M. (2009). DL-Lite with Temporalised Concepts, Rigid Axioms and Roles. In: Ghilardi, S., Sebastiani, R. (eds) Frontiers of Combining Systems. FroCoS 2009. Lecture Notes in Computer Science(), vol 5749. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04222-5_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-04222-5_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04221-8
Online ISBN: 978-3-642-04222-5
eBook Packages: Computer ScienceComputer Science (R0)