Complexity:Techniques

This page is outdated an no longer maintained. An up to date version of the content of this page
can now be found here: [http://cl-informatik.uibk.ac.at/users/georg/cbr/competition/].

This page is for listing all techniques applied by the participants of the complexity competitions.

Be aware: the lists are still preliminary.

Derivational Complexity

Method	2008	2009
Arctic Interpretation	Tools:CaT	Tools:CaT, Tools:TCT
Match Bounds	Tools:CaT	Tools:CaT
Matrix Interpretation Triangular	Tools:CaT, Tools:TCT	Tools:CaT, Tools:Matchbox, Tools:TCT
Matrix Interpretation Non-Triangular	---	Tools:Matchbox
Modular (Relative) Complexity Analysis	---	Tools:CaT
Rewriting Right Hand Sides	Tools:CaT	Tools:TCT
Root Labeling	Tools:CaT	Tools:CaT, Tools:TCT

Runtime Complexity

Method	2008	2009	2010
Arctic Interpretation	---	Tools:CaT, Tools:TCT
Match Bounds	---	Tools:CaT
Matrix Interpretation Triangular	Tools:TCT	Tools:CaT, Tools:TCT	Tools:AProVE
Matrix Interpretation Non-Triangular	---	---
Modular (Relative) Complexity Analysis	---	Tools:CaT
Polynomial Interpretations	---	---	Tools:AProVE
Polynomial Path Orders	Tools:TCT	Tools:TCT
Rewriting Right Hand Sides	---	---
Root Labeling	---	Tools:CaT, Tools:TCT
Weak Dependency Pairs	Tools:TCT	Tools:TCT
Dependency Tuples			Tools:AProVE