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	2013	2012	2011	2010	2009
Arctic Interpretation	CaT	CaT	CaT	CaT, TcT	CaT, TcT
Match Bounds	CaT, TcT	CaT, TcT	CaT, TcT	CaT, TcT	CaT, TcT
Matrix Interpretation Triangular	---	---	TcT (N)	TcT (N)	CaT (N), Matchbox (N), TcT (N)
Matrix Interpretation Non-Triangular	CaT (N,R,Q), TcT (N)	CaT (N,R,Q), TcT (N)	CaT (N,R,Q), Matchbox (N)	CaT (N,R,Q), Matchbox (N)	---
Modular (Relative) Complexity Analysis	CaT, TcT	CaT, TcT	CaT	CaT	CaT
Rewriting Right Hand Sides	---	---	---	---	TcT
Root Labeling	CaT	CaT	CaT	CaT	CaT, TcT
Weight Gap Principle	CaT, TcT	CaT, TcT	CaT, TcT	CaT, TcT	CaT

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