Theoretical Computer Science

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

Be aware: the lists are still preliminary.

Method	2009	2008
Arctic Interpretation	CaT, TcT	CaT, TcT
Match Bounds	CaT, TcT	CaT, TcT
Matrix Interpretation Triangular	CaT (N), Matchbox (N), TcT (N)	TcT (N)
Matrix Interpretation Non-Triangular	---	---
Modular (Relative) Complexity Analysis	CaT	---
Rewriting Right Hand Sides	TcT	CaT
Root Labeling	CaT, TcT	CaT
Weight Gap Principle	CaT	---

Method	2009	2008
Arctic Interpretation	CaT, TcT	---
Match Bounds	CaT, TcT	TcT
Matrix Interpretation Triangular	CaT (N), TcT (N)	TcT (N)
Matrix Interpretation Non-Triangular	---	---
Modular (Relative) Complexity Analysis	CaT	---
Polynomial Interpretations	---	---
Polynomial Path Orders	TcT	TcT
Rewriting Right Hand Sides	---	---
Root Labeling	CaT, TcT	---
Weak Dependency Pairs	TcT	TcT
Dependency Tuples	---	---
Path Analysis	TcT	TcT
Weight Gap Principle	TcT	TcT
DG Decomposition	---	---