Difference between revisions of "Complexity Techniques"

From Termination-Portal.org
Jump to navigationJump to search
(Lists broken by tools)
 
(4 intermediate revisions by 2 users not shown)
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.
  
== Derivational Complexity ==
 
  
=== 2009 ===
+
'''Be aware:''' the lists are still preliminary.
  
==== CaT (Winner of 2009) ====
+
== Derivational Complexity ==
 
 
* Triangular Matrix Interpretations
 
* Arctic Interpretations
 
* Rewriting Right Hand Sides
 
* Root Labeling
 
* Match Bounds
 
* Modular Complexity Analysis (dc(R)=dc(R1/R2)+dc(R2/R1))
 
 
 
==== Matchbox ====
 
 
 
* Triangular Matrix Interpretations
 
* Non-Triangular Matrix Interpretations
 
 
 
==== TCT ====
 
 
 
* Triangular Matrix Interpretations
 
* Arctic Interpretations
 
* Rewriting Right Hand Sides
 
* Root Labeling
 
 
 
=== 2008 ===
 
 
 
==== CaT (Winner of 2008) ====
 
 
 
* Triangular Matrix Interpretations
 
* Arctic Interpretations
 
* Rewriting Right Hand Sides
 
* Root Labeling
 
* Match Bounds
 
  
==== TCT ====
+
{| class="wikitable" border="1"
 
+
|-
* Triangular Matrix Interpretations
+
!  Method
* Root Labeling
+
!  2008
* Match Bounds
+
!  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 ==
 
== Runtime Complexity ==
  
=== 2009 ===
+
{| class="wikitable" border="1"
 
+
|-
TBA
+
!  Method
 
+
!  2008
=== 2008 ===
+
2009
 
+
|-
TBA
+
|  Arctic Interpretation
 +
|  ---
 +
|  [[Tools:CaT]], [[Tools:TCT]]
 +
|-
 +
|  Match Bounds
 +
|  ---
 +
|  [[Tools:CaT]]
 +
|-
 +
|  Matrix Interpretation Triangular
 +
|  [[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
 +
|  ---
 +
|  ---
 +
|-
 +
|  Root Labeling
 +
|  ---
 +
|  [[Tools:CaT]], [[Tools:TCT]]
 +
|-
 +
|  Weak Dependency Pairs
 +
|  [[Tools:TCT]]
 +
|  [[Tools:TCT]]
 +
|}

Latest revision as of 07:58, 29 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:TCT
Match Bounds --- Tools:CaT
Matrix Interpretation Triangular 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 --- ---
Root Labeling --- Tools:CaT, Tools:TCT
Weak Dependency Pairs Tools:TCT Tools:TCT