YES(?,O(n^1)) 705.32/297.12 YES(?,O(n^1)) 705.32/297.12 705.32/297.12 We are left with following problem, upon which TcT provides the 705.32/297.12 certificate YES(?,O(n^1)). 705.32/297.12 705.32/297.12 Strict Trs: 705.32/297.12 { c(c(x)) -> b(c(b(c(x)))) 705.32/297.12 , c(c(b(c(x)))) -> b(a(0(), c(x))) 705.32/297.12 , a(0(), x) -> c(c(x)) } 705.32/297.12 Obligation: 705.32/297.12 innermost runtime complexity 705.32/297.12 Answer: 705.32/297.12 YES(?,O(n^1)) 705.32/297.12 705.32/297.12 The problem is match-bounded by 2. The enriched problem is 705.32/297.12 compatible with the following automaton. 705.32/297.12 { c_0(2) -> 1 705.32/297.12 , c_1(2) -> 3 705.32/297.12 , c_1(3) -> 1 705.32/297.12 , c_2(2) -> 6 705.32/297.12 , c_2(5) -> 4 705.32/297.12 , b_0(2) -> 2 705.32/297.12 , b_2(4) -> 1 705.32/297.12 , b_2(6) -> 5 705.32/297.12 , a_0(2, 2) -> 1 705.32/297.12 , 0_0() -> 2 } 705.32/297.12 705.32/297.12 Hurray, we answered YES(?,O(n^1)) 705.32/297.17 EOF