Jump to content

Complexity Techniques: Difference between revisions

From Termination-Portal.org
Aschnabl (talk | contribs)
Added techniques (I know of) for derivational complexity
 
Aschnabl (talk | contribs)
Lists broken by tools
Line 5: Line 5:
=== 2009 ===
=== 2009 ===


* everything from 2008
==== CaT (Winner of 2009) ====
 
* 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
* Non-Triangular Matrix Interpretations
* Modular Complexity Analysis (dc(R)=dc(R1/R2)+dc(R2/R1))
 
==== TCT ====
 
* Triangular Matrix Interpretations
* Arctic Interpretations
* Rewriting Right Hand Sides
* Root Labeling


=== 2008 ===
=== 2008 ===
==== CaT (Winner of 2008) ====


* Triangular Matrix Interpretations
* Triangular Matrix Interpretations
* Arctic Interpretations
* Arctic Interpretations
* Rewriting Right Hand Sides
* Rewriting Right Hand Sides
* Root Labeling
* Match Bounds
==== TCT ====
* Triangular Matrix Interpretations
* Root Labeling
* Root Labeling
* Match Bounds
* Match Bounds

Revision as of 12:33, 26 March 2010

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

Derivational Complexity

2009

CaT (Winner of 2009)

  • 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

  • Triangular Matrix Interpretations
  • Root Labeling
  • Match Bounds

Runtime Complexity

2009

TBA

2008

TBA