YES Problem: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) Proof: DP Processor: DPs: foldB#(t,s(n)) -> foldB#(t,n) foldB#(t,s(n)) -> f#(foldB(t,n),B()) foldC#(t,s(n)) -> foldC#(t,n) foldC#(t,s(n)) -> f#(foldC(t,n),C()) f#(t,x) -> g#(x) f#(t,x) -> f'#(t,g(x)) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b) f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b)) f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) fold#(t,x,s(n)) -> fold#(t,x,n) fold#(t,x,s(n)) -> f#(fold(t,x,n),x) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) TDG Processor: DPs: foldB#(t,s(n)) -> foldB#(t,n) foldB#(t,s(n)) -> f#(foldB(t,n),B()) foldC#(t,s(n)) -> foldC#(t,n) foldC#(t,s(n)) -> f#(foldC(t,n),C()) f#(t,x) -> g#(x) f#(t,x) -> f'#(t,g(x)) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b) f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b)) f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) fold#(t,x,s(n)) -> fold#(t,x,n) fold#(t,x,s(n)) -> f#(fold(t,x,n),x) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) graph: fold#(t,x,s(n)) -> fold#(t,x,n) -> fold#(t,x,s(n)) -> f#(fold(t,x,n),x) fold#(t,x,s(n)) -> fold#(t,x,n) -> fold#(t,x,s(n)) -> fold#(t,x,n) fold#(t,x,s(n)) -> f#(fold(t,x,n),x) -> f#(t,x) -> f'#(t,g(x)) fold#(t,x,s(n)) -> f#(fold(t,x,n),x) -> f#(t,x) -> g#(x) f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) -> foldC#(t,s(n)) -> f#(foldC(t,n),C()) f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) -> foldC#(t,s(n)) -> foldC#(t,n) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) -> f#(t,x) -> f'#(t,g(x)) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) -> f#(t,x) -> g#(x) f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b)) -> f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b) -> foldB#(t,s(n)) -> f#(foldB(t,n),B()) f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b) -> foldB#(t,s(n)) -> foldB#(t,n) foldC#(t,s(n)) -> foldC#(t,n) -> foldC#(t,s(n)) -> f#(foldC(t,n),C()) foldC#(t,s(n)) -> foldC#(t,n) -> foldC#(t,s(n)) -> foldC#(t,n) foldC#(t,s(n)) -> f#(foldC(t,n),C()) -> f#(t,x) -> f'#(t,g(x)) foldC#(t,s(n)) -> f#(foldC(t,n),C()) -> f#(t,x) -> g#(x) f#(t,x) -> f'#(t,g(x)) -> f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b)) f#(t,x) -> f'#(t,g(x)) -> f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b) f#(t,x) -> f'#(t,g(x)) -> f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) foldB#(t,s(n)) -> f#(foldB(t,n),B()) -> f#(t,x) -> f'#(t,g(x)) foldB#(t,s(n)) -> f#(foldB(t,n),B()) -> f#(t,x) -> g#(x) foldB#(t,s(n)) -> foldB#(t,n) -> foldB#(t,s(n)) -> f#(foldB(t,n),B()) foldB#(t,s(n)) -> foldB#(t,n) -> foldB#(t,s(n)) -> foldB#(t,n) SCC Processor: #sccs: 2 #rules: 10 #arcs: 22/144 DPs: fold#(t,x,s(n)) -> fold#(t,x,n) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) Subterm Criterion Processor: simple projection: pi(fold#) = 2 problem: DPs: TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) Qed DPs: f#(t,x) -> f'#(t,g(x)) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b) foldB#(t,s(n)) -> foldB#(t,n) foldB#(t,s(n)) -> f#(foldB(t,n),B()) f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b)) f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) foldC#(t,s(n)) -> foldC#(t,n) foldC#(t,s(n)) -> f#(foldC(t,n),C()) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) Arctic Interpretation Processor: dimension: 1 interpretation: [f''#](x0) = x0 + 5, [f'#](x0, x1) = x0 + x1 + 0, [foldC#](x0, x1) = x0 + 5, [f#](x0, x1) = x0 + x1 + 0, [foldB#](x0, x1) = 3x0 + x1 + 0, [fold](x0, x1, x2) = x0 + x1 + 4, [f''](x0) = x0 + 2, [triple](x0, x1, x2) = 1x1, [f'](x0, x1) = x0 + 2, [foldC](x0, x1) = x0 + 2, [f](x0, x1) = x0 + 2, [s](x0) = 1x0 + 5, [foldB](x0, x1) = x0 + 1x1 + 0, [0] = 0, [C] = 5, [B] = 5, [g](x0) = x0 + 0, [A] = 5 orientation: f#(t,x) = t + x + 0 >= t + x + 0 = f'#(t,g(x)) f'#(triple(a,b,c),B()) = 1b + 5 >= 1b + 5 = f#(triple(a,b,c),A()) f'#(triple(a,b,c),A()) = 1b + 5 >= b + 4 = foldB#(triple(s(a),0(),c),b) foldB#(t,s(n)) = 1n + 3t + 5 >= n + 3t + 0 = foldB#(t,n) foldB#(t,s(n)) = 1n + 3t + 5 >= 1n + t + 5 = f#(foldB(t,n),B()) f'#(triple(a,b,c),A()) = 1b + 5 >= 1b + 5 = f''#(foldB(triple(s(a),0(),c),b)) f''#(triple(a,b,c)) = 1b + 5 >= 1b + 5 = foldC#(triple(a,b,0()),c) foldC#(t,s(n)) = t + 5 >= t + 5 = foldC#(t,n) foldC#(t,s(n)) = t + 5 >= t + 5 = f#(foldC(t,n),C()) g(A()) = 5 >= 5 = A() g(B()) = 5 >= 5 = A() g(B()) = 5 >= 5 = B() g(C()) = 5 >= 5 = A() g(C()) = 5 >= 5 = B() g(C()) = 5 >= 5 = C() foldB(t,0()) = t + 1 >= t = t foldB(t,s(n)) = 2n + t + 6 >= 1n + t + 2 = f(foldB(t,n),B()) foldC(t,0()) = t + 2 >= t = t foldC(t,s(n)) = t + 2 >= t + 2 = f(foldC(t,n),C()) f(t,x) = t + 2 >= t + 2 = f'(t,g(x)) f'(triple(a,b,c),C()) = 1b + 2 >= 1b = triple(a,b,s(c)) f'(triple(a,b,c),B()) = 1b + 2 >= 1b + 2 = f(triple(a,b,c),A()) f'(triple(a,b,c),A()) = 1b + 2 >= 1b + 2 = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = 1b + 2 >= 1b + 2 = foldC(triple(a,b,0()),c) fold(t,x,0()) = t + x + 4 >= t = t fold(t,x,s(n)) = t + x + 4 >= t + x + 4 = f(fold(t,x,n),x) problem: DPs: f#(t,x) -> f'#(t,g(x)) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) foldB#(t,s(n)) -> foldB#(t,n) foldB#(t,s(n)) -> f#(foldB(t,n),B()) f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b)) f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) foldC#(t,s(n)) -> foldC#(t,n) foldC#(t,s(n)) -> f#(foldC(t,n),C()) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) SCC Processor: #sccs: 2 #rules: 7 #arcs: 15/64 DPs: foldB#(t,s(n)) -> foldB#(t,n) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) Subterm Criterion Processor: simple projection: pi(foldB#) = 1 problem: DPs: TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) Qed DPs: f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) foldC#(t,s(n)) -> foldC#(t,n) foldC#(t,s(n)) -> f#(foldC(t,n),C()) f#(t,x) -> f'#(t,g(x)) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b)) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) Matrix Interpretation Processor: dim=1 interpretation: [f''#](x0) = 2x0 + 1/2, [f'#](x0, x1) = 2x0 + 1/2, [foldC#](x0, x1) = 2x0 + 2x1 + 1/2, [f#](x0, x1) = 2x0 + 1/2, [fold](x0, x1, x2) = 2x0 + 2x1 + 5/2x2 + 1, [f''](x0) = x0 + 2, [triple](x0, x1, x2) = 3/2x1 + x2, [f'](x0, x1) = x0 + 2, [foldC](x0, x1) = x0 + x1 + 2, [f](x0, x1) = x0 + 2, [s](x0) = x0 + 2, [foldB](x0, x1) = x0 + 3/2x1, [0] = 0, [C] = 0, [B] = 0, [g](x0) = 0, [A] = 0 orientation: f''#(triple(a,b,c)) = 3b + 2c + 1/2 >= 3b + 2c + 1/2 = foldC#(triple(a,b,0()),c) foldC#(t,s(n)) = 2n + 2t + 9/2 >= 2n + 2t + 1/2 = foldC#(t,n) foldC#(t,s(n)) = 2n + 2t + 9/2 >= 2n + 2t + 9/2 = f#(foldC(t,n),C()) f#(t,x) = 2t + 1/2 >= 2t + 1/2 = f'#(t,g(x)) f'#(triple(a,b,c),B()) = 3b + 2c + 1/2 >= 3b + 2c + 1/2 = f#(triple(a,b,c),A()) f'#(triple(a,b,c),A()) = 3b + 2c + 1/2 >= 3b + 2c + 1/2 = f''#(foldB(triple(s(a),0(),c),b)) g(A()) = 0 >= 0 = A() g(B()) = 0 >= 0 = A() g(B()) = 0 >= 0 = B() g(C()) = 0 >= 0 = A() g(C()) = 0 >= 0 = B() g(C()) = 0 >= 0 = C() foldB(t,0()) = t >= t = t foldB(t,s(n)) = 3/2n + t + 3 >= 3/2n + t + 2 = f(foldB(t,n),B()) foldC(t,0()) = t + 2 >= t = t foldC(t,s(n)) = n + t + 4 >= n + t + 4 = f(foldC(t,n),C()) f(t,x) = t + 2 >= t + 2 = f'(t,g(x)) f'(triple(a,b,c),C()) = 3/2b + c + 2 >= 3/2b + c + 2 = triple(a,b,s(c)) f'(triple(a,b,c),B()) = 3/2b + c + 2 >= 3/2b + c + 2 = f(triple(a,b,c),A()) f'(triple(a,b,c),A()) = 3/2b + c + 2 >= 3/2b + c + 2 = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = 3/2b + c + 2 >= 3/2b + c + 2 = foldC(triple(a,b,0()),c) fold(t,x,0()) = 2t + 2x + 1 >= t = t fold(t,x,s(n)) = 5/2n + 2t + 2x + 6 >= 5/2n + 2t + 2x + 3 = f(fold(t,x,n),x) problem: DPs: f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) foldC#(t,s(n)) -> f#(foldC(t,n),C()) f#(t,x) -> f'#(t,g(x)) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b)) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) Matrix Interpretation Processor: dim=1 interpretation: [f''#](x0) = x0 + 1, [f'#](x0, x1) = x0 + 1, [foldC#](x0, x1) = x0 + x1, [f#](x0, x1) = x0 + 1, [fold](x0, x1, x2) = x0 + x1 + x2, [f''](x0) = x0, [triple](x0, x1, x2) = x1 + x2, [f'](x0, x1) = x0 + 1, [foldC](x0, x1) = x0 + x1, [f](x0, x1) = x0 + 1, [s](x0) = x0 + 1, [foldB](x0, x1) = x0 + x1, [0] = 0, [C] = 0, [B] = 0, [g](x0) = 0, [A] = 0 orientation: f''#(triple(a,b,c)) = b + c + 1 >= b + c = foldC#(triple(a,b,0()),c) foldC#(t,s(n)) = n + t + 1 >= n + t + 1 = f#(foldC(t,n),C()) f#(t,x) = t + 1 >= t + 1 = f'#(t,g(x)) f'#(triple(a,b,c),B()) = b + c + 1 >= b + c + 1 = f#(triple(a,b,c),A()) f'#(triple(a,b,c),A()) = b + c + 1 >= b + c + 1 = f''#(foldB(triple(s(a),0(),c),b)) g(A()) = 0 >= 0 = A() g(B()) = 0 >= 0 = A() g(B()) = 0 >= 0 = B() g(C()) = 0 >= 0 = A() g(C()) = 0 >= 0 = B() g(C()) = 0 >= 0 = C() foldB(t,0()) = t >= t = t foldB(t,s(n)) = n + t + 1 >= n + t + 1 = f(foldB(t,n),B()) foldC(t,0()) = t >= t = t foldC(t,s(n)) = n + t + 1 >= n + t + 1 = f(foldC(t,n),C()) f(t,x) = t + 1 >= t + 1 = f'(t,g(x)) f'(triple(a,b,c),C()) = b + c + 1 >= b + c + 1 = triple(a,b,s(c)) f'(triple(a,b,c),B()) = b + c + 1 >= b + c + 1 = f(triple(a,b,c),A()) f'(triple(a,b,c),A()) = b + c + 1 >= b + c = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = b + c >= b + c = foldC(triple(a,b,0()),c) fold(t,x,0()) = t + x >= t = t fold(t,x,s(n)) = n + t + x + 1 >= n + t + x + 1 = f(fold(t,x,n),x) problem: DPs: foldC#(t,s(n)) -> f#(foldC(t,n),C()) f#(t,x) -> f'#(t,g(x)) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) f'#(triple(a,b,c),A()) -> f''#(foldB(triple(s(a),0(),c),b)) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) SCC Processor: #sccs: 1 #rules: 2 #arcs: 9/16 DPs: f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) f#(t,x) -> f'#(t,g(x)) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) Arctic Interpretation Processor: dimension: 1 interpretation: [f'#](x0, x1) = 1x1 + 0, [f#](x0, x1) = x0 + 2x1 + 3, [fold](x0, x1, x2) = 5x0 + x1 + 1x2 + 0, [f''](x0) = x0 + 0, [triple](x0, x1, x2) = 4, [f'](x0, x1) = 4, [foldC](x0, x1) = x0 + 4, [f](x0, x1) = x0 + x1 + 4, [s](x0) = 5x0 + 3, [foldB](x0, x1) = x0 + 4, [0] = 0, [C] = 4, [B] = 3, [g](x0) = x0 + 1, [A] = 0 orientation: f'#(triple(a,b,c),B()) = 4 >= 4 = f#(triple(a,b,c),A()) f#(t,x) = t + 2x + 3 >= 1x + 2 = f'#(t,g(x)) g(A()) = 1 >= 0 = A() g(B()) = 3 >= 0 = A() g(B()) = 3 >= 3 = B() g(C()) = 4 >= 0 = A() g(C()) = 4 >= 3 = B() g(C()) = 4 >= 4 = C() foldB(t,0()) = t + 4 >= t = t foldB(t,s(n)) = t + 4 >= t + 4 = f(foldB(t,n),B()) foldC(t,0()) = t + 4 >= t = t foldC(t,s(n)) = t + 4 >= t + 4 = f(foldC(t,n),C()) f(t,x) = t + x + 4 >= 4 = f'(t,g(x)) f'(triple(a,b,c),C()) = 4 >= 4 = triple(a,b,s(c)) f'(triple(a,b,c),B()) = 4 >= 4 = f(triple(a,b,c),A()) f'(triple(a,b,c),A()) = 4 >= 4 = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = 4 >= 4 = foldC(triple(a,b,0()),c) fold(t,x,0()) = 5t + x + 1 >= t = t fold(t,x,s(n)) = 6n + 5t + x + 4 >= 1n + 5t + x + 4 = f(fold(t,x,n),x) problem: DPs: f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) TRS: g(A()) -> A() g(B()) -> A() g(B()) -> B() g(C()) -> A() g(C()) -> B() g(C()) -> C() foldB(t,0()) -> t foldB(t,s(n)) -> f(foldB(t,n),B()) foldC(t,0()) -> t foldC(t,s(n)) -> f(foldC(t,n),C()) f(t,x) -> f'(t,g(x)) f'(triple(a,b,c),C()) -> triple(a,b,s(c)) f'(triple(a,b,c),B()) -> f(triple(a,b,c),A()) f'(triple(a,b,c),A()) -> f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) -> foldC(triple(a,b,0()),c) fold(t,x,0()) -> t fold(t,x,s(n)) -> f(fold(t,x,n),x) SCC Processor: #sccs: 0 #rules: 0 #arcs: 2/1