Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings

Publication: Research - peer-reviewJournal article – Annual report year: 2010

View graph of relations

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.
Original languageEnglish
JournalElectronic Notes in Theoretical Computer Science
Publication date2010
Volume262
Pages65-81
ISSN1571-0661
DOIs
StatePublished
CitationsWeb of Science® Times Cited: No match on DOI

Keywords

  • interval temporal logics, overlap relation, undecidability, octant tiling problem
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 4870525