The dark side of interval temporal logic: marking the undecidability border

Davide Bresolin, Dario Della Monica, Valentin Goranko, Angelo Montanari, Guido Sciavicco

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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.
Original languageEnglish
JournalAnnals of Mathematics and Artificial Intelligence
Volume71
Issue number1-3
Pages (from-to)41-83
Number of pages43
ISSN1012-2443
DOIs
Publication statusPublished - 2014

Keywords

  • Interval temporal logic
  • Tiling problems
  • Undecidability

Fingerprint Dive into the research topics of 'The dark side of interval temporal logic: marking the undecidability border'. Together they form a unique fingerprint.

Cite this