Jump to content

Complexity Techniques: Difference between revisions

From Termination-Portal.org
Hzankl (talk | contribs)
corrected 2009 cat methods
Hzankl (talk | contribs)
Line 34: Line 34:
|  Rewriting Right Hand Sides
|  Rewriting Right Hand Sides
|  [[Tools:CaT]]
|  [[Tools:CaT]]
|  [[Tools:CaT]], [[Tools:TCT]]
|  [[Tools:TCT]]
|-
|-
|  Root Labeling
|  Root Labeling
Line 40: Line 40:
|  [[Tools:CaT]], [[Tools:TCT]]
|  [[Tools:CaT]], [[Tools:TCT]]
|}
|}


== Runtime Complexity ==
== Runtime Complexity ==

Revision as of 18:41, 27 March 2010

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
Arctic Interpretation Tools:CaT Tools:CaT, Tools:TCT
Match Bounds Tools:CaT Tools:CaT
Matrix Interpretation Triangular Tools:CaT, Tools:TCT Tools:CaT, Tools:TCT
Matrix Interpretation Non-Triangular --- ---
Modular (Relative) Complexity Analysis --- Tools:CaT
Polynomial Path Orders Tools:TCT Tools:TCT
Rewriting Right Hand Sides Tools:CaT ---
Root Labeling Tools:CaT Tools:CaT, Tools:TCT
Weak Dependency Pairs Tools:TCT Tools:TCT