This page provides the current rules for the complexity competition as updated for termcomp 2015; an earlier version, focussing on upper bounds, can be found here.

Rules of the Competition

Input Format

Problems are given in the newly TPDB-format, cf. Termination-Portal. where the XML-element problem will have the type complexity given. Further, depending on the category DC, iDC, RC and iRC, the attributes strategy and startterm will be set to FULL/INNERMOST and full/constructor-based respectively.

Output Format

The output format is adapted so that additional information on the asymptotic complexity is given for lower as well as upper bounds. Hence the output written to the first line of STDOUT shall be a complexity statement according to the following grammar:

S -> MAYBE | WORST_CASE(L,U) | WORST_CASE(?,U) | WORST_CASE(L,?)
L -> Omega(n^Nat) | NON_POLY
U -> O(1) | O(n^Nat) | POLY

where "Nat" is a non-zero natural number and WORST_CASE(L,U) means L (U) is a lower (upper) bound. Here "Omega(n^k)" is the usual Omega notation and "NON_POLY" refers to an unspecified exponential. On the other hand "O(n^k)" is the usual big-Oh notation and "POLY" indicates an unspecified polynomial. Either of the functions L, U (but not both) may be replaced by "don't know", indicated by ?. Any remaining output on STDOUT will be considered as proof output and has to follow the normal rules for the competition.

Rewriting Modulo

In all categories relative rewriting rules are supported. While the semantics of relative rewriting is clear for full rewriting, there is a choice howto define relative rewriting in the innermost case: in order to innermost rewrite R modulo S, we employ innermost rewriting with respect to the union of R and S.

Scoring

Scoring is for lower and upper bounds. We make use of two linear orders, one for upper bounds and one for lower bounds. The minimal element for upper bounds is "O(1)", the maximal "?". With respect to lower bounds the minimal element is "NON_POLY". Again the maximal element is "?". Trivial answers count as "?", i.e. a linear lower bound is the same as "don't know" for the subcategory DC. The following scoring algorithm is used.

Firstly, given k answers (low1,up1) … (low_k,up_k) on a specific TRS, two rankings are determined, for lower and upper bounds independently. For the lower bounds ranking, the best tool(s) get k points, the second best tool(s) get k-1 points, etc, where giving the trivial answer always gives 0 points. Similarly, each tool gets the points for the upper bounds ranking. And the final score is just the sum of the points for upper and lower bounds.

Secondly, all resulting points for all considered systems are summed up and the contestant with the highest number of points wins. If this cannot establish a winner, there are multiple winners.

Problem Sets and Problem Selection

Testbeds

All authors of complexity tools that participated in the last complexity competition agreed upon the following selection of examples from the TPDB. For simplicity, we decided on using the same testbed for full and innermost rewriting. However, we decided on two separate testbeds for derivational and runtime complexity analysis. The testbeds are described below in detail, additionally a list of problems for TPDB version 8.0 is provided for RC and DC. For the individual subcategories RC, RCi, DC and DCi all strategy and start-term annotations should be overwritten appropriately. Thus we simply ignore for instance context-sensitive strategies.

Derivational Complexity

Since TPDB 9.0, the problem sets for the four currently considered subcategories (DC, iDC, RC, and iRC) are provided within the TPDB. Here only one instance of duplicated problems (modulo strategy annotations) is considered, and certain examples that admit trivial complexity upper bounds are removed.

Test Cases

In the following test cases we restrict to full rewriting.

R = {a(b(x)) -> b(a(x))} 
    expected output: e.g. "WORST_CASE(?,O(n^2))" or "WORST_CASE(Omega(n^2),O(n^3))".

R = {a(a(x)) -> b(c(x)), b(b(x)) -> a(c(x)), c(c(x)) -> a(b(x))}
    expected output: e.g. "WORST_CASE(Omega(n^2),O(n^2))" or "WORST_CASE(Omega(n^2),?)".

R = {+(s(x),+(y,z)) -> +(x,+(s(s(y)),z)), +(s(x),+(y,+(z,w))) -> +(x,+(z,+(y,w)))}
    expected output: "WORST_CASE(NON_POLY,?)" or "MAYBE".

test cases - runtime complexity

R = {a(b(x)) -> b(b(a(x)))}
    expected output: e.g. "WORST_CASE(?,O(n^1))" or "WORST_CASE(Omega(n^1),O(n^1))"

R = {plus(0,y) -> y, plus(s(x),y) -> s(plus(x,y)), mul(0,y) -> 0, 
    mul(s(x),y) -> plus(mul(x,y),y)}
    expected output: e.g. "WORST_CASE(?,O(n^2))" or "WORST_CASE(Omega(n^2),O(n^2))".

R = {f(x,0) -> s(0), f(s(x),s(y)) -> s(f(x,y)), g(0,x) -> g(f(x,x),x)}
    expected output: "WORST_CASE(?,O(n^1))" or "WORST_CASE(Omega(n^1),O(n^1))".

R = {f(0) -> c, f(s(x)) -> c(f(x),f(x))}
    expected output: e.g. "WORST_CASE(NON_POLY,?)"

In the following test cases we restrict to innermost rewriting.

test cases - derivational complexity

R = {f(x) -> c(x,x)}
    expected output: e.g. "WORST_CASE(Omega(n^1),O(n^1))" or "WORST_CASE(?,O(n^1))"

test cases - runtime complexity

R = {f(x) -> c(x,x), g(0) -> 0, g(s(x)) -> f(g(x))}
    expected output: e.g. "WORST_CASE(Omega(n^1),O(n^1))" or "WORST_CASE(?,O(n^1))"