Optimal Tableau Decision Procedures for PDL

Details Optimal Tableau Decision Procedures for PDL Optimal Tableau Decision Procedures for PDL

2009-04-04

arxiv.org/abs/0904.0721v2

Fund. Inform. 104(4), pp. 349-384, 2010

Computer Science

Logic in Computer Science

Scientific paper

We reformulate Pratt's tableau decision procedure of checking satisfiability of a set of formulas in PDL. Our formulation is simpler and more direct for implementation. Extending the method we give the first EXPTIME (optimal) tableau decision procedure not based on transformation for checking consistency of an ABox w.r.t. a TBox in PDL (here, PDL is treated as a description logic). We also prove the new result that the data complexity of the instance checking problem in PDL is coNP-complete.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-123298