Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings | Zendy

Davide Bresolin | Zendy; Dario Della Monica | Zendy; Valentin Goranko | Zendy; Angelo Montanari | Zendy; Guido Sciavicco | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings

Author(s) -

Davide Bresolin,

Dario Della Monica,

Valentin Goranko,

Angelo Montanari,

Guido Sciavicco

Publication year - 2010

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2010.04.006

Subject(s) - undecidable problem , decidability , modal operator , mathematics , satisfiability , interval (graph theory) , discrete mathematics , modal logic , interval temporal logic , class (philosophy) , relation (database) , combinatorics , modal , algorithm , linear temporal logic , computer science , chemistry , artificial intelligence , database , polymer chemistry

The 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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research