Techniques

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


Be aware: the lists are still preliminary.

Derivational Complexity

next year or prev year

Method 20232022202120202019
Arctic Interpretation
Match Bounds
Matrix Interpretation Triangular
Matrix Interpretation Non-Triangular
Modular (Relative) Complexity Analysis
Rewriting Right Hand Sides
Root Labeling
Weight Gap Principle

Runtime Complexity

next year or prev year

Method 20162015201420132012
Arctic InterpretationCaTCaTCaT
Match BoundsAProVE, CaT, TcTAProVE, CaT, TcTAProVE, CaT, TcT
Matrix Interpretation TriangularAProVE (N)AProVE (N)AProVE (N)
Matrix Interpretation Non-Triangular CaT (N,R,Q),
TcT (N)		CaT (N,R,Q),
TcT (N)		CaT (N,R,Q),
TcT (N)
Modular (Relative) Complexity AnalysisAProVE, CaT, TcTAProVE, CaT, TcTAProVE, CaT, TcT
Polynomial InterpretationsAProVE (N),
TcT (N)		AProVE (N),
TcT (N)		AProVE (N),
TcT (N)
Polynomial Path OrdersTcT (sPOP*)TcT (sPOP*)TcT (sPOP*)
Rewriting Right Hand SidesAProVEAProVEAProVE
Root Labeling---------
Weak Dependency PairsTcTTcTTcT
Dependency TuplesAProVE, TcTAProVE, TcTAProVE, TcT
Path AnalysisTcTTcTTcT
Weight Gap PrincipleCaT, TcTCaT, TcTCaT, TcT
DG DecompositionTcTTcTTcT