Difference between revisions of "Complexity Techniques"

From Termination-Portal.org
Jump to navigationJump to search
Line 1: Line 1:
 
This page is for listing all techniques applied by the participants of the complexity competitions.
 
This page is for listing all techniques applied by the participants of the complexity competitions.
 +
 +
 +
'''Be aware:''' the lists are still preliminary.
 +
 +
== Derivational Complexity ==
  
 
{| class="wikitable" border="1"
 
{| class="wikitable" border="1"
Line 6: Line 11:
 
!  2008
 
!  2008
 
!  2009
 
!  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
 
|  Matrix Interpretation Non-Triangular
Line 11: Line 28:
 
|  [[Tools:Matchbox]]
 
|  [[Tools:Matchbox]]
 
|-
 
|-
Matrix Interpretation Triangular
+
Modular (Relative) Complexity Analysis
 +
|  ---
 +
|  [[Tools:CaT]]
 +
|-
 +
|  Rewriting Right Hand Sides
 +
|  [[Tools:CaT]]
 
|  [[Tools:CaT]], [[Tools:TCT]]
 
|  [[Tools:CaT]], [[Tools:TCT]]
|  [[Tools:CaT]], [[Tools:Matchbox]], [[Tools:TCT]]
 
 
|-
 
|-
Arctic Interpretation
+
Root Labeling
 
|  [[Tools:CaT]]
 
|  [[Tools:CaT]]
 
|  [[Tools:CaT]], [[Tools:TCT]]
 
|  [[Tools:CaT]], [[Tools:TCT]]
 +
|}
 +
 +
 +
== Runtime Complexity ==
 +
 +
{| class="wikitable" border="1"
 
|-
 
|-
Root Labeling
+
!  Method
 +
!  2008
 +
!  2009
 +
|-
 +
Arctic Interpretation
 
|  [[Tools:CaT]]
 
|  [[Tools:CaT]]
 
|  [[Tools:CaT]], [[Tools:TCT]]
 
|  [[Tools:CaT]], [[Tools:TCT]]
 
|-
 
|-
Rewriting Right Hand Sides
+
Match Bounds
 +
|  [[Tools:CaT]]
 
|  [[Tools:CaT]]
 
|  [[Tools:CaT]]
 +
|-
 +
|  Matrix Interpretation Triangular
 
|  [[Tools:CaT]], [[Tools:TCT]]
 
|  [[Tools:CaT]], [[Tools:TCT]]
 +
|  [[Tools:CaT]], [[Tools:TCT]]
 +
|-
 +
|  Matrix Interpretation Non-Triangular
 +
|  ---
 +
|  ---
 
|-
 
|-
 
|  Modular (Relative) Complexity Analysis
 
|  Modular (Relative) Complexity Analysis
Line 31: Line 70:
 
|  [[Tools:CaT]]
 
|  [[Tools:CaT]]
 
|-
 
|-
Match Bounds
+
Polynomial Path Orders
 +
|  [[Tools:TCT]]
 +
|  [[Tools:TCT]]
 +
|-
 +
|  Rewriting Right Hand Sides
 +
|  [[Tools:CaT]]
 
|  [[Tools:CaT]]
 
|  [[Tools:CaT]]
 +
|-
 +
|  Root Labeling
 
|  [[Tools:CaT]]
 
|  [[Tools:CaT]]
 +
|  [[Tools:CaT]], [[Tools:TCT]]
 +
|-
 +
|  Weak Dependency Pairs
 +
|  [[Tools:TCT]]
 +
|  [[Tools:TCT]]
 
|}
 
|}
 
== Runtime Complexity ==
 
 
=== 2009 ===
 
 
TBA
 
 
=== 2008 ===
 
 
TBA
 

Revision as of 08:08, 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: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 Tools:CaT
Root Labeling Tools:CaT Tools:CaT, Tools:TCT
Weak Dependency Pairs Tools:TCT Tools:TCT