{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T11:03:50Z","timestamp":1775819030129,"version":"3.50.1"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,8,1]],"date-time":"2012-08-01T00:00:00Z","timestamp":1343779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2012,8]]},"abstract":"<jats:p>Most of the research on temporalized Description Logics (DLs) has concentrated on the case where temporal operators can be applied to concepts, and sometimes additionally to TBox axioms and ABox assertions. The aim of this article is to study temporalized DLs where temporal operators on TBox axioms and ABox assertions are available, but temporal operators on concepts are not. While the main application of existing temporalized DLs is the representation of conceptual models that explicitly incorporate temporal aspects, the family of DLs studied in this article addresses applications that focus on the temporal evolution of data and of ontologies. Our results show that disallowing temporal operators on concepts can significantly decrease the complexity of reasoning. In particular, reasoning with rigid roles (whose interpretation does not change over time) is typically undecidable without such a syntactic restriction, whereas our logics are decidable in elementary time even in the presence of rigid roles. We analyze the effects on computational complexity of dropping rigid roles, dropping rigid concepts, replacing temporal TBoxes with global ones, and restricting the set of available temporal operators. In this way, we obtain a novel family of temporalized DLs whose complexity ranges from 2- ExpTime-complete via NExpTime-complete to ExpTime-complete.<\/jats:p>","DOI":"10.1145\/2287718.2287721","type":"journal-article","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T13:09:44Z","timestamp":1346159384000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":31,"title":["LTL over description logic axioms"],"prefix":"10.1145","volume":"13","author":[{"given":"Franz","family":"Baader","sequence":"first","affiliation":[{"name":"TU Dresden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Silvio","family":"Ghilardi","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carsten","family":"Lutz","sequence":"additional","affiliation":[{"name":"University of Bremen"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,8,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622797.1622809"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016636131405"},{"key":"e_1_2_1_3_1","unstructured":"Artale A. and Franconi E. 2001. Temporal description logics. In Handbook of Time and Temporal Reasoning in Artificial Intelligence D. Gabbay M. Fisher and L. Vila Eds. The MIT Press.  Artale A. and Franconi E. 2001. Temporal description logics. In Handbook of Time and Temporal Reasoning in Artificial Intelligence D. Gabbay M. Fisher and L. Vila Eds. The MIT Press."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 8th European Workshop on Logics in Artificial Intelligence (JELIA '02)","volume":"2424","author":"Artale A.","unstructured":"Artale , A. , Franconi , E. , Wolter , F. , and Zakharyaschev , M . 2002. A temporal description logic for reasoning over conceptual schemas and queries . In Proceedings of the 8th European Workshop on Logics in Artificial Intelligence (JELIA '02) . Lecture Notes in Computer Science , vol. 2424 . Springer, 98--110. Artale, A., Franconi, E., Wolter, F., and Zakharyaschev, M. 2002. A temporal description logic for reasoning over conceptual schemas and queries. In Proceedings of the 8th European Workshop on Logics in Artificial Intelligence (JELIA '02). Lecture Notes in Computer Science, vol. 2424. Springer, 98--110."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIME.2007.62"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Workshop on Description Logics (DL '09), B. C. Grau, I. Horrocks, B. Motik, and U. Sattler, Eds., CEUR Electronic Workshop Proceedings, http:\/\/ceur-ws.org\/Vol-477\/.","author":"Artale A.","unstructured":"Artale , A. , Kontchakov , R. , Ryzhikov , V. , and Zakharyaschev , M . 2009. Extending DL-Lite sometime in the future . In Proceedings of the International Workshop on Description Logics (DL '09), B. C. Grau, I. Horrocks, B. Motik, and U. Sattler, Eds., CEUR Electronic Workshop Proceedings, http:\/\/ceur-ws.org\/Vol-477\/. Artale, A., Kontchakov, R., Ryzhikov, V., and Zakharyaschev, M. 2009. Extending DL-Lite sometime in the future. In Proceedings of the International Workshop on Description Logics (DL '09), B. C. Grau, I. Horrocks, B. Motik, and U. Sattler, Eds., CEUR Electronic Workshop Proceedings, http:\/\/ceur-ws.org\/Vol-477\/."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI '07)","author":"Artale A.","unstructured":"Artale , A. , Lutz , C. , and Toman , D . 2007b. A description logic of change . In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI '07) . 218--223. Artale, A., Lutz, C., and Toman, D. 2007b. A description logic of change. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI '07). 218--223."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Baader F. Bauer A. and \n      Lippmann M\n  . \n  2009\n  . Runtime verification using a temporal description logic. In Proceedings of the 7th International Symposium on Frontiers of Combining Systems (FroCoS '09) S. Ghilardi and R. Sebastiani Eds. Lecture Notes in Computer Science vol. \n  5749 Springer 149--164.   Baader F. Bauer A. and Lippmann M. 2009. Runtime verification using a temporal description logic. In Proceedings of the 7th International Symposium on Frontiers of Combining Systems (FroCoS '09) S. Ghilardi and R. Sebastiani Eds. Lecture Notes in Computer Science vol. 5749 Springer 149--164.","DOI":"10.1007\/978-3-642-04222-5_9"},{"key":"e_1_2_1_9_1","volume-title":"2003. The Description Logic Handbook: Theory, Implementation, and Applications","author":"Baader F.","unstructured":"Baader , F. , Calvanese , D. , McGuinness , D. , Nardi , D. , and Patel-Schneider , P. F. , Eds. 2003. The Description Logic Handbook: Theory, Implementation, and Applications . Cambridge University Press . Baader, F., Calvanese, D., McGuinness, D., Nardi, D., and Patel-Schneider, P. F., Eds. 2003. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge University Press."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR '08)","author":"Baader F.","unstructured":"Baader , F. , Ghilardi , S. , and Lutz , C . 2008. LTL over description logic axioms . In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR '08) , G. Brewka and J. Lang, Eds., Morgan Kaufmann, Los Altos, 684--694. Baader, F., Ghilardi, S., and Lutz, C. 2008. LTL over description logic axioms. In Proceedings of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR '08), G. Brewka and J. Lang, Eds., Morgan Kaufmann, Los Altos, 684--694."},{"key":"e_1_2_1_11_1","volume-title":"Modal Logic. Cambridge Tracts in Theoretical Computer Science","volume":"53","author":"Blackburn P.","unstructured":"Blackburn , P. , de Rijke , M. , and Venema , Y . 2001 . Modal Logic. Cambridge Tracts in Theoretical Computer Science , vol. 53 . Cambridge University Press. Blackburn, P., de Rijke, M., and Venema, Y. 2001. Modal Logic. Cambridge Tracts in Theoretical Computer Science, vol. 53. Cambridge University Press."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Perspectives in Mathematical Logic. Springer-Verlag.  B\u00f6rger E. Gr\u00e4del E. and Gurevich Y. 1997. The Classical Decision Problem. Perspectives in Mathematical Logic. Springer-Verlag.","DOI":"10.1007\/978-3-642-59207-2"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00156915"},{"key":"e_1_2_1_15_1","unstructured":"Gabbay D. Kurusz A. Wolter F. and Zakharyaschev M. 2003. Many-Dimensional Modal Logics: Theory and Applications. Elsevier.  Gabbay D. Kurusz A. Wolter F. and Zakharyaschev M. 2003. Many-Dimensional Modal Logics: Theory and Applications. Elsevier."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2003.07.001"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.9"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI '01)","author":"Lutz C.","year":"2001","unstructured":"Lutz , C. 2001 . Interval-based temporal reasoning with general TBoxes . In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI '01) . 89--94. Lutz, C. 2001. Interval-based temporal reasoning with general TBoxes. In Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI '01). 89--94."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIME.2008.14"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.32"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 12th International Joint Conference on Arti_cial Intelligence (IJCAI '91)","author":"Schild K.","year":"1991","unstructured":"Schild , K. 1991 . A correspondence theory for terminological logics: Preliminary report . In Proceedings of the 12th International Joint Conference on Arti_cial Intelligence (IJCAI '91) . 466--471. Schild, K. 1991. A correspondence theory for terminological logics: Preliminary report. In Proceedings of the 12th International Joint Conference on Arti_cial Intelligence (IJCAI '91). 466--471."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645374.651030"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90078-X"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 8th National Conference on Artificial Intelligence (AAAI '90)","author":"Schmiedel A.","year":"1990","unstructured":"Schmiedel , A. 1990 . A temporal terminological logic . In Proceedings of the 8th National Conference on Artificial Intelligence (AAAI '90) . 640--645. Schmiedel, A. 1990. A temporal terminological logic. In Proceedings of the 8th National Conference on Artificial Intelligence (AAAI '90). 640--645."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 1st European Conference on SNOMED CT (SMCS '06)","author":"Schulz S.","unstructured":"Schulz , S. , Mark\u00f3 , K. , and Suntisrivaraporn , B . 2006. Complex occurrents in clinical terminologies and their representation in a formal language . In Proceedings of the 1st European Conference on SNOMED CT (SMCS '06) . Schulz, S., Mark\u00f3, K., and Suntisrivaraporn, B. 2006. Complex occurrents in clinical terminologies and their representation in a formal language. In Proceedings of the 1st European Conference on SNOMED CT (SMCS '06)."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL '99)","volume":"1683","author":"Tobies S.","year":"1999","unstructured":"Tobies , S. 1999 . A NEXPTIME-complete description logic strictly contained in C2 . In Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL '99) , J. Flum and M. Rodr\u00edguez-Artalejo, Eds., Lecture Notes in Computer Science , vol. 1683 , Springer, 292--306. Tobies, S. 1999. A NEXPTIME-complete description logic strictly contained in C2. In Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL '99), J. Flum and M. Rodr\u00edguez-Artalejo, Eds., Lecture Notes in Computer Science, vol. 1683, Springer, 292--306."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1983.51"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 2nd International Workshop on Frontiers of Combining Systems (FroCoS '98)","author":"Wolter F.","unstructured":"Wolter , F. and Zakharyaschev , M . 1999. Temporalizing description logics . In Proceedings of the 2nd International Workshop on Frontiers of Combining Systems (FroCoS '98) , M. de Rijke and D. Gabbay, Eds., Wiley. Wolter, F. and Zakharyaschev, M. 1999. Temporalizing description logics. In Proceedings of the 2nd International Workshop on Frontiers of Combining Systems (FroCoS '98), M. de Rijke and D. Gabbay, Eds., Wiley."}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2287718.2287721","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2287718.2287721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:49:04Z","timestamp":1750236544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2287718.2287721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["10.1145\/2287718.2287721"],"URL":"https:\/\/doi.org\/10.1145\/2287718.2287721","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-08-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}