YES(?,O(n^1)) 0.00/0.14 YES(?,O(n^1)) 0.00/0.14 0.00/0.14 We are left with following problem, upon which TcT provides the 0.00/0.14 certificate YES(?,O(n^1)). 0.00/0.14 0.00/0.14 Strict Trs: 0.00/0.14 { and(tt(), X) -> activate(X) 0.00/0.14 , activate(X) -> X 0.00/0.14 , plus(N, 0()) -> N 0.00/0.14 , plus(N, s(M)) -> s(plus(N, M)) } 0.00/0.14 Obligation: 0.00/0.14 innermost runtime complexity 0.00/0.14 Answer: 0.00/0.14 YES(?,O(n^1)) 0.00/0.14 0.00/0.14 The input was oriented with the instance of 'Small Polynomial Path 0.00/0.14 Order (PS,1-bounded)' as induced by the safe mapping 0.00/0.14 0.00/0.14 safe(and) = {1, 2}, safe(tt) = {}, safe(activate) = {1}, 0.00/0.14 safe(plus) = {}, safe(0) = {}, safe(s) = {1} 0.00/0.14 0.00/0.14 and precedence 0.00/0.14 0.00/0.14 and > activate, plus > activate, and ~ plus . 0.00/0.14 0.00/0.14 Following symbols are considered recursive: 0.00/0.14 0.00/0.14 {and, plus} 0.00/0.14 0.00/0.14 The recursion depth is 1. 0.00/0.14 0.00/0.14 For your convenience, here are the satisfied ordering constraints: 0.00/0.14 0.00/0.14 and(; tt(), X) > activate(; X) 0.00/0.14 0.00/0.14 activate(; X) > X 0.00/0.14 0.00/0.14 plus(N, 0();) > N 0.00/0.14 0.00/0.14 plus(N, s(; M);) > s(; plus(N, M;)) 0.00/0.14 0.00/0.14 0.00/0.14 Hurray, we answered YES(?,O(n^1)) 0.00/0.15 EOF