The Light Side of Interval Temporal Logic: The Bernays-Schönfinkel's Fragment of CDT

Decidability and complexity of the satisfiability problem for the logics of time intervals have been extensively studied in the last years. Even though most interval logics turnout to be undecidable, meaningful exceptions exist, such as the logics of temporal neighborhood and (some of) the logics of...

Full description

Saved in:
Bibliographic Details
Main Authors: Bresolin, D., Monica, D. D., Montanari, A., Sciavicco, G.
Format: Conference Proceeding
Language:English
Subjects:
complexity
Computer science
decidability
Educational institutions
Electronic mail
Grammar
inteval temporal logics
Semantics
Syntactics
tableaux methods
Vocabulary
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Decidability and complexity of the satisfiability problem for the logics of time intervals have been extensively studied in the last years. Even though most interval logics turnout to be undecidable, meaningful exceptions exist, such as the logics of temporal neighborhood and (some of) the logics of the subinterval relation. In this paper, we explore a different path to decidability: instead of restricting the set of modalities or imposing suitable semantic restrictions, we take the most expressive interval temporal logic studied so far, namely, Venema's CDT, and we suitably limit the nesting degree of modalities. The decidability of the satisfiability problem for the resulting CDT fragment is proved by embedding it into a well-known decidable prefix quantifier class of first-order logic, namely, the Bernays-Schonfinkel's class. In addition, we show that such a fragment is in fact NP-complete (theBernays-Schonfinkel's class is NEXPTIME-complete), and that any natural extension of it is undecidable.
ISSN:1530-1311
2332-6468
DOI:10.1109/TIME.2011.20