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 20142013201220112010
Arctic InterpretationCaTCaTCaTCaTCaT, TcT
Match BoundsCaT, TcTCaT, TcTCaT, TcTCaT, TcTCaT, TcT
Matrix Interpretation Triangular---------TcT (N)TcT (N)
Matrix Interpretation Non-Triangular CaT (N,R,Q),
TcT (N)
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 AnalysisCaT, TcTCaT, TcTCaT, TcTCaTCaT
Rewriting Right Hand Sides---------------
Root LabelingCaTCaTCaTCaTCaT
Weight Gap PrincipleCaT, TcTCaT, TcTCaT, TcTCaT, TcTCaT, TcT

Runtime Complexity

next year or prev year

Method 20132012201120102009
Arctic InterpretationCaTCaTCaTCaTCaT, TcT
Match BoundsAProVE, CaT, TcTAProVE, CaT, TcTCaT, TcTCaT, TcTCaT, TcT
Matrix Interpretation TriangularAProVE (N)AProVE (N)AProVE (N),
TcT (N)
AProVE (N),
TcT (N)
CaT (N), TcT (N)
Matrix Interpretation Non-Triangular CaT (N,R,Q),
TcT (N)
CaT (N,R,Q),
TcT (N)
CaT (N,R,Q)CaT (N,R,Q)---
Modular (Relative) Complexity AnalysisAProVE, CaT, TcTAProVE, CaT, TcTAProVE, CaTAProVE, CaTCaT
Polynomial InterpretationsAProVE (N),
TcT (N)
AProVE (N),
TcT (N)
AProVE (N)AProVE (N)---
Polynomial Path OrdersTcT (sPOP*)TcT (sPOP*)TcTTcTTcT
Rewriting Right Hand SidesAProVEAProVEAProVEAProVE---
Root Labeling------------CaT, TcT
Weak Dependency PairsTcTTcTTcTTcTTcT
Dependency TuplesAProVE, TcTAProVE, TcTAProVE, TcTAProVE---
Path AnalysisTcTTcTTcTTcTTcT
Weight Gap PrincipleCaT, TcTCaT, TcTCaT, TcTCaT, TcTTcT
DG DecompositionTcTTcT---------