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