Complexity Techniques

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

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