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
Retrieved from "http://termination-portal.org/mediawiki/index.php?title=Complexity_Techniques&oldid=1056"