Difference between revisions of "Complexity Techniques"
From Termination-Portal.org
Jump to navigationJump to search (Lists broken by tools) |
|||
(4 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
This page is for listing all techniques applied by the participants of the complexity competitions. | This page is for listing all techniques applied by the participants of the complexity competitions. | ||
− | |||
− | + | '''Be aware:''' the lists are still preliminary. | |
− | == | + | == Derivational Complexity == |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | == | + | {| class="wikitable" border="1" |
− | + | |- | |
− | + | ! Method | |
− | + | ! 2008 | |
− | + | ! 2009 | |
+ | |- | ||
+ | | Arctic Interpretation | ||
+ | | [[Tools:CaT]] | ||
+ | | [[Tools:CaT]], [[Tools:TCT]] | ||
+ | |- | ||
+ | | Match Bounds | ||
+ | | [[Tools:CaT]] | ||
+ | | [[Tools:CaT]] | ||
+ | |- | ||
+ | | Matrix Interpretation Triangular | ||
+ | | [[Tools:CaT]], [[Tools:TCT]] | ||
+ | | [[Tools:CaT]], [[Tools:Matchbox]], [[Tools:TCT]] | ||
+ | |- | ||
+ | | Matrix Interpretation Non-Triangular | ||
+ | | --- | ||
+ | | [[Tools:Matchbox]] | ||
+ | |- | ||
+ | | Modular (Relative) Complexity Analysis | ||
+ | | --- | ||
+ | | [[Tools:CaT]] | ||
+ | |- | ||
+ | | Rewriting Right Hand Sides | ||
+ | | [[Tools:CaT]] | ||
+ | | [[Tools:TCT]] | ||
+ | |- | ||
+ | | Root Labeling | ||
+ | | [[Tools:CaT]] | ||
+ | | [[Tools:CaT]], [[Tools:TCT]] | ||
+ | |} | ||
== Runtime Complexity == | == Runtime Complexity == | ||
− | == | + | {| class="wikitable" border="1" |
− | + | |- | |
− | + | ! Method | |
− | + | ! 2008 | |
− | + | ! 2009 | |
− | + | |- | |
− | + | | Arctic Interpretation | |
+ | | --- | ||
+ | | [[Tools:CaT]], [[Tools:TCT]] | ||
+ | |- | ||
+ | | Match Bounds | ||
+ | | --- | ||
+ | | [[Tools:CaT]] | ||
+ | |- | ||
+ | | Matrix Interpretation Triangular | ||
+ | | [[Tools:TCT]] | ||
+ | | [[Tools:CaT]], [[Tools:TCT]] | ||
+ | |- | ||
+ | | Matrix Interpretation Non-Triangular | ||
+ | | --- | ||
+ | | --- | ||
+ | |- | ||
+ | | Modular (Relative) Complexity Analysis | ||
+ | | --- | ||
+ | | [[Tools:CaT]] | ||
+ | |- | ||
+ | | Polynomial Path Orders | ||
+ | | [[Tools:TCT]] | ||
+ | | [[Tools:TCT]] | ||
+ | |- | ||
+ | | Rewriting Right Hand Sides | ||
+ | | --- | ||
+ | | --- | ||
+ | |- | ||
+ | | Root Labeling | ||
+ | | --- | ||
+ | | [[Tools:CaT]], [[Tools:TCT]] | ||
+ | |- | ||
+ | | Weak Dependency Pairs | ||
+ | | [[Tools:TCT]] | ||
+ | | [[Tools:TCT]] | ||
+ | |} |
Latest revision as of 07:58, 29 March 2010
This page is for listing all techniques applied by the participants of the complexity competitions.
Be aware: the lists are still preliminary.
Derivational Complexity
Method | 2008 | 2009 |
---|---|---|
Arctic Interpretation | Tools:CaT | Tools:CaT, Tools:TCT |
Match Bounds | Tools:CaT | Tools:CaT |
Matrix Interpretation Triangular | Tools:CaT, Tools:TCT | Tools:CaT, Tools:Matchbox, Tools:TCT |
Matrix Interpretation Non-Triangular | --- | Tools:Matchbox |
Modular (Relative) Complexity Analysis | --- | Tools:CaT |
Rewriting Right Hand Sides | Tools:CaT | Tools:TCT |
Root Labeling | Tools:CaT | Tools:CaT, Tools:TCT |
Runtime Complexity
Method | 2008 | 2009 |
---|---|---|
Arctic Interpretation | --- | Tools:CaT, Tools:TCT |
Match Bounds | --- | Tools:CaT |
Matrix Interpretation Triangular | Tools:TCT | Tools:CaT, Tools:TCT |
Matrix Interpretation Non-Triangular | --- | --- |
Modular (Relative) Complexity Analysis | --- | Tools:CaT |
Polynomial Path Orders | Tools:TCT | Tools:TCT |
Rewriting Right Hand Sides | --- | --- |
Root Labeling | --- | Tools:CaT, Tools:TCT |
Weak Dependency Pairs | Tools:TCT | Tools:TCT |