YES(?,O(n^1)) 5.93/1.88 YES(?,O(n^1)) 5.93/1.88 5.93/1.88 We are left with following problem, upon which TcT provides the 5.93/1.88 certificate YES(?,O(n^1)). 5.93/1.88 5.93/1.88 Strict Trs: 5.93/1.88 { f(a(), a()) -> f(a(), b()) 5.93/1.88 , f(a(), b()) -> f(s(a()), c()) 5.93/1.88 , f(s(X), c()) -> f(X, c()) 5.93/1.88 , f(c(), c()) -> f(a(), a()) } 5.93/1.88 Obligation: 5.93/1.88 innermost runtime complexity 5.93/1.88 Answer: 5.93/1.88 YES(?,O(n^1)) 5.93/1.88 5.93/1.88 The problem is match-bounded by 4. The enriched problem is 5.93/1.88 compatible with the following automaton. 5.93/1.88 { f_0(2, 2) -> 1 5.93/1.88 , f_1(2, 4) -> 1 5.93/1.88 , f_1(3, 3) -> 1 5.93/1.88 , f_1(3, 4) -> 1 5.93/1.88 , f_2(3, 6) -> 1 5.93/1.88 , f_2(5, 6) -> 1 5.93/1.88 , f_2(7, 9) -> 1 5.93/1.88 , f_3(7, 8) -> 1 5.93/1.88 , f_4(10, 11) -> 1 5.93/1.88 , a_0() -> 2 5.93/1.88 , a_1() -> 3 5.93/1.88 , a_2() -> 7 5.93/1.88 , a_3() -> 10 5.93/1.88 , b_0() -> 2 5.93/1.88 , b_1() -> 4 5.93/1.88 , b_2() -> 9 5.93/1.88 , s_0(2) -> 2 5.93/1.88 , s_1(3) -> 3 5.93/1.88 , s_2(7) -> 5 5.93/1.88 , s_3(10) -> 7 5.93/1.88 , c_0() -> 2 5.93/1.88 , c_1() -> 4 5.93/1.88 , c_2() -> 6 5.93/1.88 , c_3() -> 8 5.93/1.88 , c_4() -> 11 } 5.93/1.88 5.93/1.88 Hurray, we answered YES(?,O(n^1)) 5.93/1.89 EOF