MAYBE We are left with following problem, upon which TcT provides the certificate MAYBE. Strict Trs: { min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , max(x, 0()) -> x , max(0(), y) -> y , max(s(x), s(y)) -> s(max(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , p(s(x)) -> x , f(s(x), s(y)) -> f(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))) } Obligation: innermost runtime complexity Answer: MAYBE We add following dependency tuples: Strict DPs: { min^#(x, 0()) -> c_1() , min^#(0(), y) -> c_2() , min^#(s(x), s(y)) -> c_3(min^#(x, y)) , max^#(x, 0()) -> c_4() , max^#(0(), y) -> c_5() , max^#(s(x), s(y)) -> c_6(max^#(x, y)) , twice^#(0()) -> c_7() , twice^#(s(x)) -> c_8(twice^#(x)) , -^#(x, 0()) -> c_9() , -^#(s(x), s(y)) -> c_10(-^#(x, y)) , p^#(s(x)) -> c_11() , f^#(s(x), s(y)) -> c_12(f^#(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))), -^#(max(s(x), s(y)), min(s(x), s(y))), max^#(s(x), s(y)), min^#(s(x), s(y)), p^#(twice(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: { min^#(x, 0()) -> c_1() , min^#(0(), y) -> c_2() , min^#(s(x), s(y)) -> c_3(min^#(x, y)) , max^#(x, 0()) -> c_4() , max^#(0(), y) -> c_5() , max^#(s(x), s(y)) -> c_6(max^#(x, y)) , twice^#(0()) -> c_7() , twice^#(s(x)) -> c_8(twice^#(x)) , -^#(x, 0()) -> c_9() , -^#(s(x), s(y)) -> c_10(-^#(x, y)) , p^#(s(x)) -> c_11() , f^#(s(x), s(y)) -> c_12(f^#(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))), -^#(max(s(x), s(y)), min(s(x), s(y))), max^#(s(x), s(y)), min^#(s(x), s(y)), p^#(twice(min(x, y))), twice^#(min(x, y)), min^#(x, y)) } Weak Trs: { min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , max(x, 0()) -> x , max(0(), y) -> y , max(s(x), s(y)) -> s(max(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , p(s(x)) -> x , f(s(x), s(y)) -> f(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))) } Obligation: innermost runtime complexity Answer: MAYBE We estimate the number of application of {1,2,4,5,7,9,11} by applications of Pre({1,2,4,5,7,9,11}) = {3,6,8,10,12}. Here rules are labeled as follows: DPs: { 1: min^#(x, 0()) -> c_1() , 2: min^#(0(), y) -> c_2() , 3: min^#(s(x), s(y)) -> c_3(min^#(x, y)) , 4: max^#(x, 0()) -> c_4() , 5: max^#(0(), y) -> c_5() , 6: max^#(s(x), s(y)) -> c_6(max^#(x, y)) , 7: twice^#(0()) -> c_7() , 8: twice^#(s(x)) -> c_8(twice^#(x)) , 9: -^#(x, 0()) -> c_9() , 10: -^#(s(x), s(y)) -> c_10(-^#(x, y)) , 11: p^#(s(x)) -> c_11() , 12: f^#(s(x), s(y)) -> c_12(f^#(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))), -^#(max(s(x), s(y)), min(s(x), s(y))), max^#(s(x), s(y)), min^#(s(x), s(y)), p^#(twice(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: { min^#(s(x), s(y)) -> c_3(min^#(x, y)) , max^#(s(x), s(y)) -> c_6(max^#(x, y)) , twice^#(s(x)) -> c_8(twice^#(x)) , -^#(s(x), s(y)) -> c_10(-^#(x, y)) , f^#(s(x), s(y)) -> c_12(f^#(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))), -^#(max(s(x), s(y)), min(s(x), s(y))), max^#(s(x), s(y)), min^#(s(x), s(y)), p^#(twice(min(x, y))), twice^#(min(x, y)), min^#(x, y)) } Weak DPs: { min^#(x, 0()) -> c_1() , min^#(0(), y) -> c_2() , max^#(x, 0()) -> c_4() , max^#(0(), y) -> c_5() , twice^#(0()) -> c_7() , -^#(x, 0()) -> c_9() , p^#(s(x)) -> c_11() } Weak Trs: { min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , max(x, 0()) -> x , max(0(), y) -> y , max(s(x), s(y)) -> s(max(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , p(s(x)) -> x , f(s(x), s(y)) -> f(-(max(s(x), s(y)), min(s(x), s(y))), p(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. { min^#(x, 0()) -> c_1() , min^#(0(), y) -> c_2() , max^#(x, 0()) -> c_4() , max^#(0(), y) -> c_5() , twice^#(0()) -> c_7() , -^#(x, 0()) -> c_9() , p^#(s(x)) -> c_11() } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { min^#(s(x), s(y)) -> c_3(min^#(x, y)) , max^#(s(x), s(y)) -> c_6(max^#(x, y)) , twice^#(s(x)) -> c_8(twice^#(x)) , -^#(s(x), s(y)) -> c_10(-^#(x, y)) , f^#(s(x), s(y)) -> c_12(f^#(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))), -^#(max(s(x), s(y)), min(s(x), s(y))), max^#(s(x), s(y)), min^#(s(x), s(y)), p^#(twice(min(x, y))), twice^#(min(x, y)), min^#(x, y)) } Weak Trs: { min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , max(x, 0()) -> x , max(0(), y) -> y , max(s(x), s(y)) -> s(max(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , p(s(x)) -> x , f(s(x), s(y)) -> f(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))) } Obligation: innermost runtime complexity Answer: MAYBE Due to missing edges in the dependency-graph, the right-hand sides of following rules could be simplified: { f^#(s(x), s(y)) -> c_12(f^#(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))), -^#(max(s(x), s(y)), min(s(x), s(y))), max^#(s(x), s(y)), min^#(s(x), s(y)), p^#(twice(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: { min^#(s(x), s(y)) -> c_1(min^#(x, y)) , max^#(s(x), s(y)) -> c_2(max^#(x, y)) , twice^#(s(x)) -> c_3(twice^#(x)) , -^#(s(x), s(y)) -> c_4(-^#(x, y)) , f^#(s(x), s(y)) -> c_5(f^#(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))), -^#(max(s(x), s(y)), min(s(x), s(y))), max^#(s(x), s(y)), min^#(s(x), s(y)), twice^#(min(x, y)), min^#(x, y)) } Weak Trs: { min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , max(x, 0()) -> x , max(0(), y) -> y , max(s(x), s(y)) -> s(max(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , p(s(x)) -> x , f(s(x), s(y)) -> f(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))) } Obligation: innermost runtime complexity Answer: MAYBE We replace rewrite rules by usable rules: Weak Usable Rules: { min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , max(x, 0()) -> x , max(0(), y) -> y , max(s(x), s(y)) -> s(max(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , p(s(x)) -> x } We are left with following problem, upon which TcT provides the certificate MAYBE. Strict DPs: { min^#(s(x), s(y)) -> c_1(min^#(x, y)) , max^#(s(x), s(y)) -> c_2(max^#(x, y)) , twice^#(s(x)) -> c_3(twice^#(x)) , -^#(s(x), s(y)) -> c_4(-^#(x, y)) , f^#(s(x), s(y)) -> c_5(f^#(-(max(s(x), s(y)), min(s(x), s(y))), p(twice(min(x, y)))), -^#(max(s(x), s(y)), min(s(x), s(y))), max^#(s(x), s(y)), min^#(s(x), s(y)), twice^#(min(x, y)), min^#(x, y)) } Weak Trs: { min(x, 0()) -> 0() , min(0(), y) -> 0() , min(s(x), s(y)) -> s(min(x, y)) , max(x, 0()) -> x , max(0(), y) -> y , max(s(x), s(y)) -> s(max(x, y)) , twice(0()) -> 0() , twice(s(x)) -> s(s(twice(x))) , -(x, 0()) -> x , -(s(x), s(y)) -> -(x, y) , p(s(x)) -> x } Obligation: innermost runtime complexity Answer: MAYBE The input cannot be shown compatible Arrrr..