Complexity Techniques

From Termination-Portal.org
Revision as of 12:25, 26 March 2010 by Aschnabl (talk | contribs) (Added techniques (I know of) for derivational complexity)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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

Derivational Complexity

2009

  • everything from 2008
  • Non-Triangular Matrix Interpretations
  • Modular Complexity Analysis (dc(R)=dc(R1/R2)+dc(R2/R1))

2008

  • Triangular Matrix Interpretations
  • Arctic Interpretations
  • Rewriting Right Hand Sides
  • Root Labeling
  • Match Bounds

Runtime Complexity

2009

TBA

2008

TBA

Retrieved from "http://termination-portal.org/mediawiki/index.php?title=Complexity_Techniques&oldid=1049"