YES(?,O(n^1)) 0.00/0.46 YES(?,O(n^1)) 0.00/0.46 0.00/0.46 We are left with following problem, upon which TcT provides the 0.00/0.46 certificate YES(?,O(n^1)). 0.00/0.46 0.00/0.46 Strict Trs: 0.00/0.46 { f(0()) -> s(0()) 0.00/0.46 , f(s(0())) -> s(s(0())) 0.00/0.46 , f(s(0())) -> *(s(s(0())), f(0())) 0.00/0.46 , f(+(x, y)) -> *(f(x), f(y)) 0.00/0.46 , f(+(x, s(0()))) -> +(s(s(0())), f(x)) } 0.00/0.46 Obligation: 0.00/0.46 runtime complexity 0.00/0.46 Answer: 0.00/0.46 YES(?,O(n^1)) 0.00/0.46 0.00/0.46 The input is overlay and right-linear. Switching to innermost 0.00/0.46 rewriting. 0.00/0.46 0.00/0.46 We are left with following problem, upon which TcT provides the 0.00/0.46 certificate YES(?,O(n^1)). 0.00/0.46 0.00/0.46 Strict Trs: 0.00/0.46 { f(0()) -> s(0()) 0.00/0.46 , f(s(0())) -> s(s(0())) 0.00/0.46 , f(s(0())) -> *(s(s(0())), f(0())) 0.00/0.46 , f(+(x, y)) -> *(f(x), f(y)) 0.00/0.46 , f(+(x, s(0()))) -> +(s(s(0())), f(x)) } 0.00/0.46 Obligation: 0.00/0.46 innermost runtime complexity 0.00/0.46 Answer: 0.00/0.46 YES(?,O(n^1)) 0.00/0.46 0.00/0.46 The problem is match-bounded by 2. The enriched problem is 0.00/0.46 compatible with the following automaton. 0.00/0.46 { f_0(2) -> 1 0.00/0.46 , f_1(2) -> 1 0.00/0.46 , f_1(2) -> 4 0.00/0.46 , f_1(3) -> 4 0.00/0.46 , 0_0() -> 2 0.00/0.46 , 0_1() -> 3 0.00/0.46 , 0_2() -> 5 0.00/0.46 , s_0(2) -> 2 0.00/0.46 , s_1(1) -> 1 0.00/0.46 , s_1(3) -> 1 0.00/0.46 , s_1(3) -> 4 0.00/0.46 , s_1(4) -> 4 0.00/0.46 , s_2(5) -> 4 0.00/0.46 , *_0(2, 2) -> 2 0.00/0.46 , *_1(1, 4) -> 1 0.00/0.46 , *_1(4, 4) -> 4 0.00/0.46 , +_0(2, 2) -> 2 0.00/0.46 , +_1(1, 4) -> 1 0.00/0.46 , +_1(1, 4) -> 4 } 0.00/0.46 0.00/0.46 Hurray, we answered YES(?,O(n^1)) 0.00/0.46 EOF