Jump to content

Complexity Techniques: Difference between revisions

From Termination-Portal.org
Aschnabl (talk | contribs)
Lists broken by tools
Zini (talk | contribs)
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 ==
{| class="wikitable" border="1"
 
|-
=== 2009 ===
!  Method
 
!  2008
==== CaT (Winner of 2009) ====
!  2009
 
|-
* Triangular Matrix Interpretations
|  Matrix Interpretation Non-Triangular
* Arctic Interpretations
|  ---
* Rewriting Right Hand Sides
|  [[Tools:Matchbox]]
* Root Labeling
|-
* Match Bounds
|  Matrix Interpretation Triangular
* Modular Complexity Analysis (dc(R)=dc(R1/R2)+dc(R2/R1))
|  [[Tools:CaT]], [[Tools:TCT]]
 
|  [[Tools:CaT]], [[Tools:Matchbox]], [[Tools:TCT]]
==== Matchbox ====
|-
 
|  Arctic Interpretation
* Triangular Matrix Interpretations
|  [[Tools:CaT]]
* Non-Triangular Matrix Interpretations
|  [[Tools:CaT]], [[Tools:TCT]]
 
|-
==== TCT ====
|  Root Labeling
 
|  [[Tools:CaT]]
* Triangular Matrix Interpretations
|  [[Tools:CaT]], [[Tools:TCT]]
* Arctic Interpretations
|-
* Rewriting Right Hand Sides
|  Rewriting Right Hand Sides
* Root Labeling
|  [[Tools:CaT]]
 
|  [[Tools:CaT]], [[Tools:TCT]]
=== 2008 ===
|-
 
|  Modular (Relative) Complexity Analysis
==== CaT (Winner of 2008) ====
|  ---
 
|  [[Tools:CaT]]
* Triangular Matrix Interpretations
|-
* Arctic Interpretations
|  Match Bounds
* Rewriting Right Hand Sides
|  [[Tools:CaT]]
* Root Labeling
|  [[Tools:CaT]]
* Match Bounds
|}
 
==== TCT ====
 
* Triangular Matrix Interpretations
* Root Labeling
* Match Bounds


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

Revision as of 07:50, 27 March 2010

This page is for listing all techniques applied by the participants of the complexity competitions.

Method 2008 2009
Matrix Interpretation Non-Triangular --- Tools:Matchbox
Matrix Interpretation Triangular Tools:CaT, Tools:TCT Tools:CaT, Tools:Matchbox, Tools:TCT
Arctic Interpretation Tools:CaT Tools:CaT, Tools:TCT
Root Labeling Tools:CaT Tools:CaT, Tools:TCT
Rewriting Right Hand Sides Tools:CaT Tools:CaT, Tools:TCT
Modular (Relative) Complexity Analysis --- Tools:CaT
Match Bounds Tools:CaT Tools:CaT

Runtime Complexity

2009

TBA

2008

TBA