MAYBE We are left with following problem, upon which TcT provides the certificate MAYBE. Strict Trs: { -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , f(s(x), s(y)) -> f(-(x, min(x, y)), s(twice(min(x, y)))) , f(s(x), s(y)) -> f(-(y, min(x, y)), s(twice(min(x, y)))) } Obligation: innermost runtime complexity Answer: MAYBE We add following dependency tuples: Strict DPs: { -^#(x, 0()) -> c_1() , -^#(s(x), s(y)) -> c_2(-^#(x, y)) , min^#(x, 0()) -> c_3() , min^#(0(), y) -> c_4() , min^#(s(x), s(y)) -> c_5(min^#(x, y)) , twice^#(0()) -> c_6() , twice^#(s(x)) -> c_7(twice^#(x)) , f^#(s(x), s(y)) -> c_8(f^#(-(x, min(x, y)), s(twice(min(x, y)))), -^#(x, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) , f^#(s(x), s(y)) -> c_9(f^#(-(y, min(x, y)), s(twice(min(x, y)))), -^#(y, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) } and mark the set of starting terms. We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { -^#(x, 0()) -> c_1() , -^#(s(x), s(y)) -> c_2(-^#(x, y)) , min^#(x, 0()) -> c_3() , min^#(0(), y) -> c_4() , min^#(s(x), s(y)) -> c_5(min^#(x, y)) , twice^#(0()) -> c_6() , twice^#(s(x)) -> c_7(twice^#(x)) , f^#(s(x), s(y)) -> c_8(f^#(-(x, min(x, y)), s(twice(min(x, y)))), -^#(x, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) , f^#(s(x), s(y)) -> c_9(f^#(-(y, min(x, y)), s(twice(min(x, y)))), -^#(y, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) } Weak Trs: { -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , f(s(x), s(y)) -> f(-(x, min(x, y)), s(twice(min(x, y)))) , f(s(x), s(y)) -> f(-(y, min(x, y)), s(twice(min(x, y)))) } Obligation: innermost runtime complexity Answer: MAYBE We estimate the number of application of {1,3,4,6} by applications of Pre({1,3,4,6}) = {2,5,7,8,9}. Here rules are labeled as follows: DPs: { 1: -^#(x, 0()) -> c_1() , 2: -^#(s(x), s(y)) -> c_2(-^#(x, y)) , 3: min^#(x, 0()) -> c_3() , 4: min^#(0(), y) -> c_4() , 5: min^#(s(x), s(y)) -> c_5(min^#(x, y)) , 6: twice^#(0()) -> c_6() , 7: twice^#(s(x)) -> c_7(twice^#(x)) , 8: f^#(s(x), s(y)) -> c_8(f^#(-(x, min(x, y)), s(twice(min(x, y)))), -^#(x, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) , 9: f^#(s(x), s(y)) -> c_9(f^#(-(y, min(x, y)), s(twice(min(x, y)))), -^#(y, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { -^#(s(x), s(y)) -> c_2(-^#(x, y)) , min^#(s(x), s(y)) -> c_5(min^#(x, y)) , twice^#(s(x)) -> c_7(twice^#(x)) , f^#(s(x), s(y)) -> c_8(f^#(-(x, min(x, y)), s(twice(min(x, y)))), -^#(x, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) , f^#(s(x), s(y)) -> c_9(f^#(-(y, min(x, y)), s(twice(min(x, y)))), -^#(y, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) } Weak DPs: { -^#(x, 0()) -> c_1() , min^#(x, 0()) -> c_3() , min^#(0(), y) -> c_4() , twice^#(0()) -> c_6() } Weak Trs: { -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , f(s(x), s(y)) -> f(-(x, min(x, y)), s(twice(min(x, y)))) , f(s(x), s(y)) -> f(-(y, min(x, y)), s(twice(min(x, y)))) } Obligation: innermost runtime complexity Answer: MAYBE The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. { -^#(x, 0()) -> c_1() , min^#(x, 0()) -> c_3() , min^#(0(), y) -> c_4() , twice^#(0()) -> c_6() } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { -^#(s(x), s(y)) -> c_2(-^#(x, y)) , min^#(s(x), s(y)) -> c_5(min^#(x, y)) , twice^#(s(x)) -> c_7(twice^#(x)) , f^#(s(x), s(y)) -> c_8(f^#(-(x, min(x, y)), s(twice(min(x, y)))), -^#(x, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) , f^#(s(x), s(y)) -> c_9(f^#(-(y, min(x, y)), s(twice(min(x, y)))), -^#(y, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) } Weak Trs: { -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , f(s(x), s(y)) -> f(-(x, min(x, y)), s(twice(min(x, y)))) , f(s(x), s(y)) -> f(-(y, min(x, y)), s(twice(min(x, y)))) } Obligation: innermost runtime complexity Answer: MAYBE We replace rewrite rules by usable rules: Weak Usable Rules: { -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { -^#(s(x), s(y)) -> c_2(-^#(x, y)) , min^#(s(x), s(y)) -> c_5(min^#(x, y)) , twice^#(s(x)) -> c_7(twice^#(x)) , f^#(s(x), s(y)) -> c_8(f^#(-(x, min(x, y)), s(twice(min(x, y)))), -^#(x, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) , f^#(s(x), s(y)) -> c_9(f^#(-(y, min(x, y)), s(twice(min(x, y)))), -^#(y, min(x, y)), min^#(x, y), twice^#(min(x, y)), min^#(x, y)) } Weak Trs: { -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) } Obligation: innermost runtime complexity Answer: MAYBE The input cannot be shown compatible Arrrr..