Jump to content

Complexity Techniques: Difference between revisions

From Termination-Portal.org
Aschnabl (talk | contribs)
Lists broken by tools
Zini (talk | contribs)
 
(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