Difference between revisions of "Complexity Techniques"
From Termination-Portal.org
Jump to navigationJump to search (Added techniques (I know of) for derivational complexity) |
(Lists broken by tools) |
||
| Line 5: | Line 5: | ||
=== 2009 === | === 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 | * Non-Triangular Matrix Interpretations | ||
| − | * | + | |
| + | ==== 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.
Contents
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
