Jump to content

Complexity Techniques

From Termination-Portal.org
Revision as of 12:33, 26 March 2010 by Aschnabl (talk | contribs) (Lists broken by tools)

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