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 20132012201120102009
Arctic InterpretationCaTCaTCaTCaT, TcTCaT, TcT
Match BoundsCaT, TcTCaT, TcTCaT, TcTCaT, TcTCaT, 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 AnalysisCaT, TcTCaT, TcTCaTCaTCaT
Rewriting Right Hand Sides------------TcT
Root LabelingCaTCaTCaTCaTCaT, TcT
Weight Gap PrincipleCaT, TcTCaT, TcTCaT, TcTCaT, TcTCaT

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------