Jump to content

Complexity Techniques: Difference between revisions

From Termination-Portal.org
Zini (talk | contribs)
Zini (talk | contribs)
 
(3 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.
'''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]], [[Tools:TCT]]
|  ---
|  [[Tools:CaT]], [[Tools:Matchbox]], [[Tools:TCT]]
|  [[Tools:CaT]]
|-
|-
|  Arctic Interpretation
|  Rewriting Right Hand Sides
|  [[Tools:CaT]]
|  [[Tools:CaT]]
|  [[Tools:CaT]], [[Tools:TCT]]
|  [[Tools:TCT]]
|-
|-
|  Root Labeling
|  Root Labeling
|  [[Tools:CaT]]
|  [[Tools:CaT]]
|  [[Tools:CaT]], [[Tools:TCT]]
|}
== Runtime Complexity ==
{| class="wikitable" border="1"
|-
!  Method
!  2008
!  2009
|-
|  Arctic Interpretation
|  ---
|  [[Tools:CaT]], [[Tools:TCT]]
|  [[Tools:CaT]], [[Tools:TCT]]
|-
|-
|  Rewriting Right Hand Sides
|  Match Bounds
|  ---
|  [[Tools:CaT]]
|  [[Tools:CaT]]
|-
|  Matrix Interpretation Triangular
|  [[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 69:
|  [[Tools:CaT]]
|  [[Tools:CaT]]
|-
|-
|  Match Bounds
|  Polynomial Path Orders
|  [[Tools:CaT]]
|  [[Tools:TCT]]
|  [[Tools:CaT]]
|  [[Tools:TCT]]
|-
|  Rewriting Right Hand Sides
|  ---
|  ---
|-
|  Root Labeling
|  ---
|  [[Tools:CaT]], [[Tools:TCT]]
|-
|  Weak Dependency Pairs
|  [[Tools:TCT]]
|  [[Tools:TCT]]
|}
|}
== Runtime Complexity ==
=== 2009 ===
TBA
=== 2008 ===
TBA

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