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 20152014201320122011
Arctic InterpretationCaTCaTCaTCaT
Match BoundsCaT, TcTCaT, TcTCaT, TcTCaT, TcT
Matrix Interpretation Triangular---------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)
Modular (Relative) Complexity AnalysisCaT, TcTCaT, TcTCaT, TcTCaT
Rewriting Right Hand Sides------------
Root LabelingCaTCaTCaTCaT
Weight Gap PrincipleCaT, TcTCaT, TcTCaT, TcTCaT, TcT

Runtime Complexity

next year or prev year

Method 20142013201220112010
Arctic InterpretationCaTCaTCaTCaTCaT
Match BoundsAProVE, CaT, TcTAProVE, CaT, TcTAProVE, CaT, TcTCaT, TcTCaT, TcT
Matrix Interpretation TriangularAProVE (N)AProVE (N)AProVE (N)AProVE (N),
TcT (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)CaT (N,R,Q)
Modular (Relative) Complexity AnalysisAProVE, CaT, TcTAProVE, CaT, TcTAProVE, CaT, TcTAProVE, CaTAProVE, CaT
Polynomial InterpretationsAProVE (N),
TcT (N)
AProVE (N),
TcT (N)
AProVE (N),
TcT (N)
AProVE (N)AProVE (N)
Polynomial Path OrdersTcT (sPOP*)TcT (sPOP*)TcT (sPOP*)TcTTcT
Rewriting Right Hand SidesAProVEAProVEAProVEAProVEAProVE
Root Labeling---------------
Weak Dependency PairsTcTTcTTcTTcTTcT
Dependency TuplesAProVE, TcTAProVE, TcTAProVE, TcTAProVE, TcTAProVE
Path AnalysisTcTTcTTcTTcTTcT
Weight Gap PrincipleCaT, TcTCaT, TcTCaT, TcTCaT, TcTCaT, TcT
DG DecompositionTcTTcTTcT------