PlumX Metrics
Embed PlumX Metrics

Adding an Equivalence Relation to the Interval Logic ABB: Complexity and Expressiveness

Proceedings - Symposium on Logic in Computer Science, ISSN: 1043-6871, Page: 193-202
2013
  • 14
    Citations
  • 0
    Usage
  • 3
    Captures
  • 0
    Mentions
  • 0
    Social Media
Metric Options:   Counts1 Year3 Year

Metrics Details

  • Citations
    14
    • Citation Indexes
      14
  • Captures
    3

Conference Paper Description

Interval temporal logics provide a general frame-work for temporal representation and reasoning, where classical (point-based) linear temporal logics can be recovered as special cases. In this paper, we study the effects of the addition of an equivalence relation ~ to one of the most representative interval temporal logics, namely, the logic ̄ of Allen's relations meets, begun by, and begins. We first prove that the satisfiability problem for the resulting logic ̄ ~ remains decidable over finite linear orders, but it becomes nonprimitive recursive, while decidability is lost over N. We also show that decidability over N can be recovered by restricting to a suitable subset of models. Then, we show that ̄ ~ is expressive enough to define -regular languages, thus establishing a promising connection between interval temporal logics and extended regular languages. © 2013 IEEE.

Bibliographic Details

Provide Feedback

Have ideas for a new metric? Would you like to see something else here?Let us know