Metric Temporal Description Logics with Interval-Rigid Names

Franz Baader; Stefan Borgwardt; Patrick Koopmann; Ana Ozaki; Veronika Thost

doi:10.1145/3399443

Metric Temporal Description Logics with Interval-Rigid Names

Franz Baader, Stefan Borgwardt, Patrick Koopmann, Ana Ozaki, Veronika Thost

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

In contrast to qualitative linear temporal logics, which can be used to state that some property will eventually be satisfied, metric temporal logics allow us to formulate constraints on how long it may take until the property is satisfied. While most of the work on combining description logics (DLs) with temporal logics has concentrated on qualitative temporal logics, there is a growing interest in extending this work to the quantitative case. In this article, we complement existing results on the combination of DLs with metric temporal logics by introducing interval-rigid concept and role names. Elements included in an interval-rigid concept or role name are required to stay in it for some specified amount of time. We investigate several combinations of (metric) temporal logics with Aĝ.,'C by either allowing temporal operators only on the level of axioms or also applying them to concepts. In contrast to most existing work on the topic, we consider a timeline based on the integers and also allow assertional axioms. We show that the worst-case complexity does not increase beyond the previously known bound of 2-ExpSpace and investigate in detail how this complexity can be reduced by restricting the temporal logic and the occurrences of interval-rigid names.

Original language	English
Article number	30
Journal	ACM Transactions on Computational Logic
Volume	21
Issue number	4
DOIs	https://doi.org/10.1145/3399443
Publication status	Published - 1 Oct 2020
Externally published	Yes

Funding

This work was partially supported by the DFG in the CRC 912 (HAEC), the project BA 1122/19-1 (GOASQ), the Cluster of Excellence “Center for Advancing Electronics Dresden” (cfaed), and grant 389792660 (https://www.perspicuous-computing. science/) (TRR 248, Center for Perspicuous Computing). Authors’ addresses: F. Baader, S. Borgwardt, P. Koopmann, Institute of Theoretical Computer Science, Technische Univer-sität Dresden, Fakultät Informatik, Nöthnitzer Str. 46, 01187 Dresden, Germany; emails: {franz.baader, stefan.borgwardt, patrick.koopmann}@tu-dresden.de; A. Ozaki, Department of Informatics, University of Bergen, Postboks 7803, 5020 Bergen, Norway and KRDB Research Centre, Free University of Bozen-Bolzano, Bozen-Bolzano, Italy; email: [email protected]; V. Thost, MIT-IBM Watson AI Lab, 75 Binney Street, Cambridge, MA, 02142, USA; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1529-3785/2020/08-ART30 $15.00 https://doi.org/10.1145/3399443

Funders	Funder number
HAEC	389792660, BA 1122/19-1
Deutsche Forschungsgemeinschaft

Access to Document

10.1145/3399443

Persistent URL (handle)

Copy link address

Cite this

@article{7e08649eb56b4ed6b5f08b8e377bcd66,

title = "Metric Temporal Description Logics with Interval-Rigid Names",

abstract = "In contrast to qualitative linear temporal logics, which can be used to state that some property will eventually be satisfied, metric temporal logics allow us to formulate constraints on how long it may take until the property is satisfied. While most of the work on combining description logics (DLs) with temporal logics has concentrated on qualitative temporal logics, there is a growing interest in extending this work to the quantitative case. In this article, we complement existing results on the combination of DLs with metric temporal logics by introducing interval-rigid concept and role names. Elements included in an interval-rigid concept or role name are required to stay in it for some specified amount of time. We investigate several combinations of (metric) temporal logics with Aĝ.,'C by either allowing temporal operators only on the level of axioms or also applying them to concepts. In contrast to most existing work on the topic, we consider a timeline based on the integers and also allow assertional axioms. We show that the worst-case complexity does not increase beyond the previously known bound of 2-ExpSpace and investigate in detail how this complexity can be reduced by restricting the temporal logic and the occurrences of interval-rigid names.",

author = "Franz Baader and Stefan Borgwardt and Patrick Koopmann and Ana Ozaki and Veronika Thost",

year = "2020",

month = oct,

day = "1",

doi = "10.1145/3399443",

language = "English",

volume = "21",

journal = "ACM Transactions on Computational Logic",

issn = "1529-3785",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Metric Temporal Description Logics with Interval-Rigid Names

AU - Baader, Franz

AU - Borgwardt, Stefan

AU - Koopmann, Patrick

AU - Ozaki, Ana

AU - Thost, Veronika

PY - 2020/10/1

Y1 - 2020/10/1

N2 - In contrast to qualitative linear temporal logics, which can be used to state that some property will eventually be satisfied, metric temporal logics allow us to formulate constraints on how long it may take until the property is satisfied. While most of the work on combining description logics (DLs) with temporal logics has concentrated on qualitative temporal logics, there is a growing interest in extending this work to the quantitative case. In this article, we complement existing results on the combination of DLs with metric temporal logics by introducing interval-rigid concept and role names. Elements included in an interval-rigid concept or role name are required to stay in it for some specified amount of time. We investigate several combinations of (metric) temporal logics with Aĝ.,'C by either allowing temporal operators only on the level of axioms or also applying them to concepts. In contrast to most existing work on the topic, we consider a timeline based on the integers and also allow assertional axioms. We show that the worst-case complexity does not increase beyond the previously known bound of 2-ExpSpace and investigate in detail how this complexity can be reduced by restricting the temporal logic and the occurrences of interval-rigid names.

AB - In contrast to qualitative linear temporal logics, which can be used to state that some property will eventually be satisfied, metric temporal logics allow us to formulate constraints on how long it may take until the property is satisfied. While most of the work on combining description logics (DLs) with temporal logics has concentrated on qualitative temporal logics, there is a growing interest in extending this work to the quantitative case. In this article, we complement existing results on the combination of DLs with metric temporal logics by introducing interval-rigid concept and role names. Elements included in an interval-rigid concept or role name are required to stay in it for some specified amount of time. We investigate several combinations of (metric) temporal logics with Aĝ.,'C by either allowing temporal operators only on the level of axioms or also applying them to concepts. In contrast to most existing work on the topic, we consider a timeline based on the integers and also allow assertional axioms. We show that the worst-case complexity does not increase beyond the previously known bound of 2-ExpSpace and investigate in detail how this complexity can be reduced by restricting the temporal logic and the occurrences of interval-rigid names.

UR - http://www.scopus.com/inward/record.url?scp=85096521308&partnerID=8YFLogxK

U2 - 10.1145/3399443

DO - 10.1145/3399443

M3 - Article

SN - 1529-3785

VL - 21

JO - ACM Transactions on Computational Logic

JF - ACM Transactions on Computational Logic

IS - 4

M1 - 30

ER -

Metric Temporal Description Logics with Interval-Rigid Names

Abstract

Funding

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this