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