An Optimal Decision Procedure for MPNL over the Integers

Details An Optimal Decision Procedure for MPNL over the Integers An Optimal Decision Procedure for MPNL over the Integers

2011-06-07

arxiv.org/abs/1106.1241v1

EPTCS 54, 2011, pp. 192-206

Computer Science

Logic in Computer Science

In Proceedings GandALF 2011, arXiv:1106.0814

Scientific paper

10.4204/EPTCS.54.14

Interval temporal logics provide a natural framework for qualitative and quantitative temporal reason- ing over interval structures, where the truth of formulae is defined over intervals rather than points. In this paper, we study the complexity of the satisfiability problem for Metric Propositional Neigh- borhood Logic (MPNL). MPNL features two modalities to access intervals "to the left" and "to the right" of the current one, respectively, plus an infinite set of length constraints. MPNL, interpreted over the naturals, has been recently shown to be decidable by a doubly exponential procedure. We improve such a result by proving that MPNL is actually EXPSPACE-complete (even when length constraints are encoded in binary), when interpreted over finite structures, the naturals, and the in- tegers, by developing an EXPSPACE decision procedure for MPNL over the integers, which can be easily tailored to finite linear orders and the naturals (EXPSPACE-hardness was already known).

Affiliated with

Also associated with

No associations

Rating

An Optimal Decision Procedure for MPNL over the Integers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Optimal Decision Procedure for MPNL over the Integers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Optimal Decision Procedure for MPNL over the Integers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-26174