An On-the-fly Tableau-based Decision Procedure for PDL-Satisfiability

Details An On-the-fly Tableau-based Decision Procedure for PDL-Satisfiability An On-the-fly Tableau-based Decision Procedure for PDL-Satisfiability

2007-11-07

arxiv.org/abs/0711.1016v2

Computer Science

Logic in Computer Science

26 pages, longer version of article in Methods for Modalities 2007; improved readability of proofs

Scientific paper

We present a tableau-based algorithm for deciding satisfiability for propositional dynamic logic (PDL) which builds a finite rooted tree with ancestor loops and passes extra information from children to parents to separate good loops from bad loops during backtracking. It is easy to implement, with potential for parallelisation, because it constructs a pseudo-model ``on the fly'' by exploring each tableau branch independently. But its worst-case behaviour is 2EXPTIME rather than EXPTIME. A prototype implementation in the TWB (http://twb.rsise.anu.edu.au) is available.

Affiliated with

Also associated with

No associations

Rating

An On-the-fly Tableau-based Decision Procedure for PDL-Satisfiability 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 On-the-fly Tableau-based Decision Procedure for PDL-Satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An On-the-fly Tableau-based Decision Procedure for PDL-Satisfiability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-502025