Back to Search
Start Over
Undecidability of the Logic of Overlap Relation over Discrete Linear Orderings
- Publication Year :
- 2010
-
Abstract
- 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.
- Subjects :
- General Computer Science
Normal modal logic
Interval temporal logic
Modal Logic
interval temporal logics
Modal operator
Interval Logic
Theoretical Computer Science
Combinatorics
Interval Temporal Logic
Undecidability
Linear temporal logic
Computer Science::Logic in Computer Science
Accessibility relation
Mathematics
Discrete mathematics
interval temporal logic
Allen's relations
undecidability
overlap relation
Modal logic
Modal μ-calculus
octant tiling problem
Decidability
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Computer Science(all)
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....9a3cfc3b20959b48da0a7add87496076