Decidable and Undecidable Fragments of Halpern and Shohams Interval Temporal Logic: Towards a Complete Classification

详细信息    查看全文

• 作者：Davide Bresolin ; Dario Della Monica ; Valentin Goranko ; Angelo Montanari ; Guido Sciavicco
• 刊名：Lecture Notes in Computer Science
• 出版年：2008
• 出版时间：2008
• 年：2008
• 卷：5330
• 期：1
• 页码：590-604
• 全文大小：568.3 KB

文摘

Interval temporal logics are based on temporal structures where time intervals, rather than time instants, are the primitive ontological entities. They employ modal operators corresponding to various relations between intervals, known as Allen’s relations. Technically, validity in interval temporal logics translates to dyadic second-order logic, thus explaining their complex computational behavior. The full modal logic of Allen’s relations, called HS, has been proved to be undecidable by Halpern and Shoham under very weak assumptions on the class of interval structures, and this result was discouraging attempts for practical applications and further research in the field. A renewed interest has been recently stimulated by the discovery of interesting decidable fragments of HS. This paper contributes to the characterization of the boundary between decidability and undecidability of HS fragments. It summarizes known positive and negative results, it describes the main techniques applied so far in both directions, and it establishes a number of new undecidability results for relatively small fragments of HS.