What's Decidable about Halpern and Shoham's Interval Logic? The Maximal Fragment ABBL

The introduction of Halpern and Shoham's modal logic of intervals (later on called HS) dates back to 1986. Despite its natural semantics, this logic is undecidable over all interesting classes of temporal structures. This discouraged research in this area until recently, when a number of non tr...

Full description

Saved in:
Bibliographic Details
Main Authors: Bresolin, D., Montanari, A., Sala, P., Sciavicco, G.
Format: Conference Proceeding
Language:English
Subjects:
Compass
Complexity
Complexity theory
Decidability
Interval Temporal Logic
Measurement uncertainty
Semantics
Syntactics
Trajectory
Vehicles
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The introduction of Halpern and Shoham's modal logic of intervals (later on called HS) dates back to 1986. Despite its natural semantics, this logic is undecidable over all interesting classes of temporal structures. This discouraged research in this area until recently, when a number of non trivial decidable fragments have been found. This paper is a contribution toward the complete classification of HS fragments. Different combinations of Allen's interval relations begins (B), meets (A), and later (L), and their inverses A̅, B̅, and L̅, have been considered in the literature. We know from previous work that the combination ABB̅A̅ is decidable over finite linear orders and undecidable everywhere else. We extend these results by showing that ABB̅L̅ is decidable over the class of all (resp., dense, discrete) linear orders, and that it is maximal with respect to decidability over these classes: adding any other interval modality immediately leads to undecidability.
ISSN:1043-6871
2575-5528
DOI:10.1109/LICS.2011.35