1 Department of Applied Mathematics and Computer Science, Technical University of Denmark2 Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark3 University of Verona4 Reykjavik University5 Department of Informatics and Mathematical Modeling, Technical University of Denmark6 University of Udine7 University of Murcia8 Reykjavik University9 University of Udine
Unlike the Moon, the dark side of interval temporal logics is the one we usually see: their ubiquitous undecidability. Identifying minimal undecidable interval logics is thus a natural and important issue in that research area. In this paper, we identify several new minimal undecidable logics amongst the fragments of Halpern and Shoham's logic HS, including the logic of the overlaps relation, over the classes of all finite linear orders and all linear orders, as well as the logic of the meets and subinterval relations, over the classes of all and dense linear orders. Together with previous undecidability results, this work contributes to bringing the identification of the dark side of interval temporal logics very close to the definitive picture.
Annals of Mathematics and Artificial Intelligence, 2014, Vol 71, Issue 1-3, p. 41-83