Jump to content

Complexity Techniques: Difference between revisions

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

Revision as of 08:08, 27 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:CaT, Tools:TCT
Root Labeling Tools:CaT Tools:CaT, Tools:TCT


Runtime 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:TCT
Matrix Interpretation Non-Triangular --- ---
Modular (Relative) Complexity Analysis --- Tools:CaT
Polynomial Path Orders Tools:TCT Tools:TCT
Rewriting Right Hand Sides Tools:CaT Tools:CaT
Root Labeling Tools:CaT Tools:CaT, Tools:TCT
Weak Dependency Pairs Tools:TCT Tools:TCT