Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders

Angelo Montanari; Ian Pratt-Hartmann; Pietro Sala

doi:10.1109/TIME.2010.18

Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders

Angelo Montanari, Ian Pratt-Hartmann, Pietro Sala

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

Abstract

An interval temporal logic is a propositional, multimodal logic interpreted over interval structures of partial orders. The semantics of each modal operator are given in the standard way with respect to one of the natural accessibility relations defined on such interval structures. In this paper, we consider the modal operators based on the (reflexive) subinterval relation and the (reflexive) super-interval relation. We show that the satisfiability problems for the interval temporal logics featuring either or both of these modalities, interpreted over interval structures of finite linear orders, are all PSPACEcomplete. These results fill a gap in the known complexity results for interval temporal logics. © 2010 IEEE.

Original language	English
Title of host publication	Proceedings - 17th International Symposium on Temporal Representation and Reasoning, TIME 2010\|Proc. - Int. Symp. Temporal Represent. Reasoning, TIME
Publisher	IEEE
Pages	27-34
Number of pages	7
ISBN (Print)	9780769541877
DOIs	https://doi.org/10.1109/TIME.2010.18
Publication status	Published - 2010
Event	17th International Symposium on Temporal Representation and Reasoning, TIME 2010 - Paris Duration: 1 Jul 2010 → …

Conference

Conference	17th International Symposium on Temporal Representation and Reasoning, TIME 2010
City	Paris
Period	1/07/10 → …

Keywords

Computational complexity
Decidability
Interval temporal logic

Access to Document

10.1109/TIME.2010.18

Cite this

Montanari, A., Pratt-Hartmann, I., & Sala, P. (2010). Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders. In Proceedings - 17th International Symposium on Temporal Representation and Reasoning, TIME 2010|Proc. - Int. Symp. Temporal Represent. Reasoning, TIME (pp. 27-34). IEEE. https://doi.org/10.1109/TIME.2010.18

@inproceedings{16de569a49b04201a90f5ddb03707712,

title = "Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders",

abstract = "An interval temporal logic is a propositional, multimodal logic interpreted over interval structures of partial orders. The semantics of each modal operator are given in the standard way with respect to one of the natural accessibility relations defined on such interval structures. In this paper, we consider the modal operators based on the (reflexive) subinterval relation and the (reflexive) super-interval relation. We show that the satisfiability problems for the interval temporal logics featuring either or both of these modalities, interpreted over interval structures of finite linear orders, are all PSPACEcomplete. These results fill a gap in the known complexity results for interval temporal logics. {\textcopyright} 2010 IEEE.",

keywords = "Computational complexity, Decidability, Interval temporal logic",

author = "Angelo Montanari and Ian Pratt-Hartmann and Pietro Sala",

year = "2010",

doi = "10.1109/TIME.2010.18",

language = "English",

isbn = "9780769541877",

pages = "27--34",

booktitle = "Proceedings - 17th International Symposium on Temporal Representation and Reasoning, TIME 2010|Proc. - Int. Symp. Temporal Represent. Reasoning, TIME",

publisher = "IEEE",

address = "United States",

note = "17th International Symposium on Temporal Representation and Reasoning, TIME 2010 ; Conference date: 01-07-2010",

}

Montanari, A, Pratt-Hartmann, I & Sala, P 2010, Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders. in Proceedings - 17th International Symposium on Temporal Representation and Reasoning, TIME 2010|Proc. - Int. Symp. Temporal Represent. Reasoning, TIME. IEEE, pp. 27-34, 17th International Symposium on Temporal Representation and Reasoning, TIME 2010, Paris, 1/07/10. https://doi.org/10.1109/TIME.2010.18

Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders. / Montanari, Angelo; Pratt-Hartmann, Ian; Sala, Pietro.
Proceedings - 17th International Symposium on Temporal Representation and Reasoning, TIME 2010|Proc. - Int. Symp. Temporal Represent. Reasoning, TIME. IEEE, 2010. p. 27-34.

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders

AU - Montanari, Angelo

AU - Pratt-Hartmann, Ian

AU - Sala, Pietro

PY - 2010

Y1 - 2010

N2 - An interval temporal logic is a propositional, multimodal logic interpreted over interval structures of partial orders. The semantics of each modal operator are given in the standard way with respect to one of the natural accessibility relations defined on such interval structures. In this paper, we consider the modal operators based on the (reflexive) subinterval relation and the (reflexive) super-interval relation. We show that the satisfiability problems for the interval temporal logics featuring either or both of these modalities, interpreted over interval structures of finite linear orders, are all PSPACEcomplete. These results fill a gap in the known complexity results for interval temporal logics. © 2010 IEEE.

AB - An interval temporal logic is a propositional, multimodal logic interpreted over interval structures of partial orders. The semantics of each modal operator are given in the standard way with respect to one of the natural accessibility relations defined on such interval structures. In this paper, we consider the modal operators based on the (reflexive) subinterval relation and the (reflexive) super-interval relation. We show that the satisfiability problems for the interval temporal logics featuring either or both of these modalities, interpreted over interval structures of finite linear orders, are all PSPACEcomplete. These results fill a gap in the known complexity results for interval temporal logics. © 2010 IEEE.

KW - Computational complexity

KW - Decidability

KW - Interval temporal logic

U2 - 10.1109/TIME.2010.18

DO - 10.1109/TIME.2010.18

M3 - Conference contribution

SN - 9780769541877

SP - 27

EP - 34

BT - Proceedings - 17th International Symposium on Temporal Representation and Reasoning, TIME 2010|Proc. - Int. Symp. Temporal Represent. Reasoning, TIME

PB - IEEE

T2 - 17th International Symposium on Temporal Representation and Reasoning, TIME 2010

Y2 - 1 July 2010

ER -

Decidability of the logics of the reflexive sub-interval and super-interval relations over finite linear orders

Abstract

Conference

Keywords

Access to Document

Fingerprint

Cite this