Automated Complexity Analysis Based on the Dependency Pair Method

Details Automated Complexity Analysis Based on the Dependency Pair Method Automated Complexity Analysis Based on the Dependency Pair Method

2011-02-15

arxiv.org/abs/1102.3129v2

Computer Science

Logic in Computer Science

37 pages, submitted to Information & Computation

Scientific paper

This article is concerned with automated complexity analysis of term rewrite systems. Since these systems underlie much of declarative programming, time complexity of functions defined by rewrite systems is of particular interest. Among other results, we present a variant of the dependency pair method for analysing runtime complexities of term rewrite systems automatically. The established results significantly extent previously known techniques: we give examples of rewrite systems subject to our methods that could previously not been analysed automatically. Furthermore, the techniques have been implemented in the Tyrolean Complexity Tool. We provide ample numerical data for assessing the viability of the method.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-378741