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 20152014201320122011
Arctic InterpretationCaTCaTCaTCaT
Match BoundsAProVE, CaT, TcTAProVE, CaT, TcTAProVE, CaT, TcTCaT, TcT
Matrix Interpretation TriangularAProVE (N)AProVE (N)AProVE (N)AProVE (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)
Modular (Relative) Complexity AnalysisAProVE, CaT, TcTAProVE, CaT, TcTAProVE, CaT, TcTAProVE, CaT
Polynomial InterpretationsAProVE (N),
TcT (N)
AProVE (N),
TcT (N)
AProVE (N),
TcT (N)
AProVE (N)
Polynomial Path OrdersTcT (sPOP*)TcT (sPOP*)TcT (sPOP*)TcT
Rewriting Right Hand SidesAProVEAProVEAProVEAProVE
Root Labeling------------
Weak Dependency PairsTcTTcTTcTTcT
Dependency TuplesAProVE, TcTAProVE, TcTAProVE, TcTAProVE, TcT
Path AnalysisTcTTcTTcTTcT
Weight Gap PrincipleCaT, TcTCaT, TcTCaT, TcTCaT, TcT
DG DecompositionTcTTcTTcT---