The Undecidability of the Logic of Subintervals

Article type: Research Article

Authors: Marcinkowski, Jerzy | Michaliszyn, Jakub

Affiliations: Institute of Computer Science, University Of Wrocław, Poland. jma@cs.uni.wroc.pl;jmi@cs.uni.wroc.pl

Note: [] Address for correspondence: Institute of Computer Science, University Of Wrocław, Poland.

Abstract: The Halpern–Shoham logic is a modal logic of time intervals. Some effort has been put in last ten years to classify fragments of this beautiful logic with respect to decidability of its satisfiability problem. We complete this classification by showing — what we believe is quite an unexpected result—that the logic of subintervals, the fragment of the Halpern–Shoham logic where only the operator “during”, or D, is allowed, is undecidable over discrete structures. This is surprising as this, apparently very simple, logic is decidable over dense orders and its reflexive variant is known to be decidable over discrete structures. Our result subsumes a lot of previous undecidability results of fragments that include D.

Keywords: Halpern–Shoham logic, logic of subintervals, undecidable logic

DOI: 10.3233/FI-2014-1011

Journal: Fundamenta Informaticae, vol. 131, no. 2, pp. 217-240, 2014