YES(O(1),O(n^1)) 0.00/0.11 YES(O(1),O(n^1)) 0.00/0.11 0.00/0.11 We are left with following problem, upon which TcT provides the 0.00/0.11 certificate YES(O(1),O(n^1)). 0.00/0.11 0.00/0.11 Strict Trs: { *(x, +(y, z)) -> +(*(x, y), *(x, z)) } 0.00/0.11 Obligation: 0.00/0.11 runtime complexity 0.00/0.11 Answer: 0.00/0.11 YES(O(1),O(n^1)) 0.00/0.11 0.00/0.11 We add the following weak dependency pairs: 0.00/0.11 0.00/0.11 Strict DPs: { *^#(x, +(y, z)) -> c_1(*^#(x, y), *^#(x, z)) } 0.00/0.11 0.00/0.11 and mark the set of starting terms. 0.00/0.11 0.00/0.11 We are left with following problem, upon which TcT provides the 0.00/0.11 certificate YES(O(1),O(n^1)). 0.00/0.11 0.00/0.11 Strict DPs: { *^#(x, +(y, z)) -> c_1(*^#(x, y), *^#(x, z)) } 0.00/0.11 Strict Trs: { *(x, +(y, z)) -> +(*(x, y), *(x, z)) } 0.00/0.11 Obligation: 0.00/0.11 runtime complexity 0.00/0.11 Answer: 0.00/0.11 YES(O(1),O(n^1)) 0.00/0.11 0.00/0.11 No rule is usable, rules are removed from the input problem. 0.00/0.11 0.00/0.11 We are left with following problem, upon which TcT provides the 0.00/0.11 certificate YES(O(1),O(n^1)). 0.00/0.11 0.00/0.11 Strict DPs: { *^#(x, +(y, z)) -> c_1(*^#(x, y), *^#(x, z)) } 0.00/0.11 Obligation: 0.00/0.11 runtime complexity 0.00/0.11 Answer: 0.00/0.11 YES(O(1),O(n^1)) 0.00/0.11 0.00/0.11 The weightgap principle applies (using the following constant 0.00/0.11 growth matrix-interpretation) 0.00/0.11 0.00/0.11 The following argument positions are usable: 0.00/0.11 Uargs(c_1) = {1, 2} 0.00/0.11 0.00/0.11 TcT has computed the following constructor-restricted matrix 0.00/0.11 interpretation. 0.00/0.11 0.00/0.11 [+](x1, x2) = [1 0] x1 + [1 0] x2 + [1] 0.00/0.11 [0 0] [0 0] [0] 0.00/0.11 0.00/0.11 [*^#](x1, x2) = [1 0] x2 + [0] 0.00/0.11 [0 0] [0] 0.00/0.11 0.00/0.11 [c_1](x1, x2) = [1 0] x1 + [1 0] x2 + [0] 0.00/0.11 [0 1] [0 1] [0] 0.00/0.11 0.00/0.11 The order satisfies the following ordering constraints: 0.00/0.11 0.00/0.11 [*^#(x, +(y, z))] = [1 0] y + [1 0] z + [1] 0.00/0.11 [0 0] [0 0] [0] 0.00/0.11 > [1 0] y + [1 0] z + [0] 0.00/0.11 [0 0] [0 0] [0] 0.00/0.11 = [c_1(*^#(x, y), *^#(x, z))] 0.00/0.11 0.00/0.11 0.00/0.11 Further, it can be verified that all rules not oriented are covered by the weightgap condition. 0.00/0.11 0.00/0.11 We are left with following problem, upon which TcT provides the 0.00/0.11 certificate YES(?,O(n^1)). 0.00/0.11 0.00/0.11 Weak DPs: { *^#(x, +(y, z)) -> c_1(*^#(x, y), *^#(x, z)) } 0.00/0.11 Obligation: 0.00/0.11 runtime complexity 0.00/0.11 Answer: 0.00/0.11 YES(?,O(n^1)) 0.00/0.11 0.00/0.11 The following weak DPs constitute a sub-graph of the DG that is 0.00/0.11 closed under successors. The DPs are removed. 0.00/0.11 0.00/0.11 { *^#(x, +(y, z)) -> c_1(*^#(x, y), *^#(x, z)) } 0.00/0.11 0.00/0.11 We are left with following problem, upon which TcT provides the 0.00/0.11 certificate YES(?,O(n^1)). 0.00/0.11 0.00/0.11 Rules: Empty 0.00/0.11 Obligation: 0.00/0.11 runtime complexity 0.00/0.11 Answer: 0.00/0.11 YES(?,O(n^1)) 0.00/0.11 0.00/0.11 We employ 'linear path analysis' using the following approximated 0.00/0.11 dependency graph: 0.00/0.11 empty 0.00/0.11 0.00/0.11 0.00/0.11 Hurray, we answered YES(O(1),O(n^1)) 0.00/0.11 EOF