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