Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings

• DOI: 10.1016/j.entcs.2010.04.006
• Publication Date: 2010-05-05T13:44:09Z
• Authors: Davide Bresolin; Dario Della Monica; Valentin Goranko; Angelo Montanari; Guido Sciavicco
• Keywords: overlap relation; Interval Temporal Logic; Modal Logic; Undecidability; undecidability; interval temporal logic; Allen's relations; undecidability; overlap relation; octant tiling problem; interval temporal logics; 0102 computer and information sciences; Interval Logic; 01 natural sciences; Theoretical Computer Science; Computer Science(all)

AbstractThe validity/satisfiability problem for most propositional interval temporal logics is (highly) undecidable, under very weak assumptions on the class of interval structures in which they are interpreted. That, in particular, holds for most fragments of Halpern and Shoham's interval modal logic HS. Still, decidability is the rule for the fragments of HS with only one modal operator, based on an Allen's relation. In this paper, we show that the logic O of the Overlap relation, when interpreted over discrete linear orderings, is an exception. The proof is based on a reduction from the undecidable octant tiling problem. This is one of the sharpest undecidability result for fragments of HS.