YES(?,O(n^1)) 0.00/0.75 YES(?,O(n^1)) 0.00/0.75 0.00/0.75 We are left with following problem, upon which TcT provides the 0.00/0.75 certificate YES(?,O(n^1)). 0.00/0.75 0.00/0.75 Strict Trs: 0.00/0.75 { f(a()) -> f(c(a())) 0.00/0.75 , f(a()) -> f(d(a())) 0.00/0.75 , f(c(X)) -> X 0.00/0.75 , f(c(a())) -> f(d(b())) 0.00/0.75 , f(c(b())) -> f(d(a())) 0.00/0.75 , f(d(X)) -> X 0.00/0.75 , e(g(X)) -> e(X) } 0.00/0.75 Obligation: 0.00/0.75 runtime complexity 0.00/0.75 Answer: 0.00/0.75 YES(?,O(n^1)) 0.00/0.75 0.00/0.75 The input is overlay and right-linear. Switching to innermost 0.00/0.75 rewriting. 0.00/0.75 0.00/0.75 We are left with following problem, upon which TcT provides the 0.00/0.75 certificate YES(?,O(n^1)). 0.00/0.75 0.00/0.75 Strict Trs: 0.00/0.75 { f(a()) -> f(c(a())) 0.00/0.75 , f(a()) -> f(d(a())) 0.00/0.75 , f(c(X)) -> X 0.00/0.75 , f(c(a())) -> f(d(b())) 0.00/0.75 , f(c(b())) -> f(d(a())) 0.00/0.75 , f(d(X)) -> X 0.00/0.75 , e(g(X)) -> e(X) } 0.00/0.75 Obligation: 0.00/0.75 innermost runtime complexity 0.00/0.75 Answer: 0.00/0.75 YES(?,O(n^1)) 0.00/0.75 0.00/0.75 The problem is match-bounded by 2. The enriched problem is 0.00/0.75 compatible with the following automaton. 0.00/0.75 { f_0(2) -> 1 0.00/0.75 , f_0(3) -> 1 0.00/0.75 , f_0(4) -> 1 0.00/0.75 , f_0(5) -> 1 0.00/0.75 , f_0(7) -> 1 0.00/0.75 , f_1(8) -> 1 0.00/0.75 , f_2(10) -> 1 0.00/0.75 , a_0() -> 1 0.00/0.75 , a_0() -> 2 0.00/0.75 , a_1() -> 1 0.00/0.75 , a_1() -> 9 0.00/0.75 , a_2() -> 1 0.00/0.75 , a_2() -> 11 0.00/0.75 , c_0(2) -> 1 0.00/0.75 , c_0(2) -> 3 0.00/0.75 , c_0(3) -> 1 0.00/0.75 , c_0(3) -> 3 0.00/0.75 , c_0(4) -> 1 0.00/0.75 , c_0(4) -> 3 0.00/0.75 , c_0(5) -> 1 0.00/0.75 , c_0(5) -> 3 0.00/0.75 , c_0(7) -> 1 0.00/0.75 , c_0(7) -> 3 0.00/0.75 , c_1(9) -> 8 0.00/0.75 , d_0(2) -> 1 0.00/0.75 , d_0(2) -> 4 0.00/0.75 , d_0(3) -> 1 0.00/0.75 , d_0(3) -> 4 0.00/0.75 , d_0(4) -> 1 0.00/0.75 , d_0(4) -> 4 0.00/0.75 , d_0(5) -> 1 0.00/0.75 , d_0(5) -> 4 0.00/0.75 , d_0(7) -> 1 0.00/0.75 , d_0(7) -> 4 0.00/0.75 , d_1(9) -> 8 0.00/0.75 , d_2(11) -> 10 0.00/0.75 , b_0() -> 1 0.00/0.75 , b_0() -> 5 0.00/0.75 , b_1() -> 1 0.00/0.75 , b_1() -> 9 0.00/0.75 , b_2() -> 1 0.00/0.75 , b_2() -> 11 0.00/0.75 , e_0(2) -> 6 0.00/0.75 , e_0(3) -> 6 0.00/0.75 , e_0(4) -> 6 0.00/0.75 , e_0(5) -> 6 0.00/0.75 , e_0(7) -> 6 0.00/0.75 , e_1(2) -> 6 0.00/0.75 , e_1(3) -> 6 0.00/0.75 , e_1(4) -> 6 0.00/0.75 , e_1(5) -> 6 0.00/0.75 , e_1(7) -> 6 0.00/0.75 , g_0(2) -> 1 0.00/0.75 , g_0(2) -> 7 0.00/0.75 , g_0(3) -> 1 0.00/0.75 , g_0(3) -> 7 0.00/0.75 , g_0(4) -> 1 0.00/0.75 , g_0(4) -> 7 0.00/0.75 , g_0(5) -> 1 0.00/0.75 , g_0(5) -> 7 0.00/0.75 , g_0(7) -> 1 0.00/0.75 , g_0(7) -> 7 } 0.00/0.75 0.00/0.75 Hurray, we answered YES(?,O(n^1)) 0.00/0.75 EOF