The Derivational Complexity Induced by the Dependency Pair Method

Details The Derivational Complexity Induced by the Dependency Pair Method The Derivational Complexity Induced by the Dependency Pair Method

2009-04-03

arxiv.org/abs/0904.0570v5

LMCS 7 (3:1) 2011

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-7(3:1)2011

We study the derivational complexity induced by the dependency pair method, enhanced with standard refinements. We obtain upper bounds on the derivational complexity induced by the dependency pair method in terms of the derivational complexity of the base techniques employed. In particular we show that the derivational complexity induced by the dependency pair method based on some direct technique, possibly refined by argument filtering, the usable rules criterion, or dependency graphs, is primitive recursive in the derivational complexity induced by the direct method. This implies that the derivational complexity induced by a standard application of the dependency pair method based on traditional termination orders like KBO, LPO, and MPO is exactly the same as if those orders were applied as the only termination technique.

Affiliated with

Also associated with

No associations

Rating

The Derivational Complexity Induced by the Dependency Pair Method 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 The Derivational Complexity Induced by the Dependency Pair Method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Derivational Complexity Induced by the Dependency Pair Method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-150784