The dark side of Interval Temporal Logic: sharpening the undecidability border

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

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    Abstract

    Unlike the Moon, the dark side of interval temporal logics is the one we usually see: their ubiquitous undesirability. Identifying minimal undecidable interval logics is thus a natural and important issue in the research agenda in the area. The decidability status of a logic often depends on the class of models (in our case, the class of interval structures)in which it is interpreted. In this paper, we have identified several new minimal undecidable logics amongst the fragments of Halpern-Shoham logic HS, including the logic of the overlaps relation, over the classes of all and finite linear orders, as well as the logic of the meet and subinterval relations, over the class of dense linear orders. Together with previous undecid ability results, this work contributes to delineate the border of the dark side of interval temporal logics quite sharply.
    Original languageEnglish
    Title of host publication2011 Eighteenth International Symposium on Temporal Representation and Reasoning (TIME)
    Publication date2011
    Pages131-138
    ISBN (Print)978-1-4577-1242-5
    DOIs
    Publication statusPublished - 2011
    Event18th International Symposium on Temporal Representation and Reasoning - Lübeck, Germany
    Duration: 12 Sep 201114 Sep 2011
    Conference number: 18
    http://www.isp.uni-luebeck.de/time11/

    Conference

    Conference18th International Symposium on Temporal Representation and Reasoning
    Number18
    CountryGermany
    CityLübeck
    Period12/09/201114/09/2011
    Internet address

    Fingerprint Dive into the research topics of 'The dark side of Interval Temporal Logic: sharpening the undecidability border'. Together they form a unique fingerprint.

    Cite this