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) EDG 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)) -> fold#(t,x,n) 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)) -> f#(fold(t,x,n),x) -> f#(t,x) -> g#(x) fold#(t,x,s(n)) -> f#(fold(t,x,n),x) -> f#(t,x) -> f'#(t,g(x)) f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) -> foldC#(t,s(n)) -> foldC#(t,n) 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),B()) -> f#(triple(a,b,c),A()) -> f#(t,x) -> g#(x) f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) -> f#(t,x) -> f'#(t,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)) -> foldB#(t,n) f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b) -> foldB#(t,s(n)) -> f#(foldB(t,n),B()) foldC#(t,s(n)) -> foldC#(t,n) -> foldC#(t,s(n)) -> foldC#(t,n) foldC#(t,s(n)) -> foldC#(t,n) -> foldC#(t,s(n)) -> f#(foldC(t,n),C()) foldC#(t,s(n)) -> f#(foldC(t,n),C()) -> f#(t,x) -> g#(x) foldC#(t,s(n)) -> f#(foldC(t,n),C()) -> f#(t,x) -> f'#(t,g(x)) f#(t,x) -> f'#(t,g(x)) -> f'#(triple(a,b,c),B()) -> f#(triple(a,b,c),A()) 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),A()) -> f''#(foldB(triple(s(a),0(),c),b)) foldB#(t,s(n)) -> f#(foldB(t,n),B()) -> f#(t,x) -> g#(x) foldB#(t,s(n)) -> f#(foldB(t,n),B()) -> f#(t,x) -> f'#(t,g(x)) foldB#(t,s(n)) -> foldB#(t,n) -> foldB#(t,s(n)) -> foldB#(t,n) foldB#(t,s(n)) -> foldB#(t,n) -> foldB#(t,s(n)) -> f#(foldB(t,n),B()) 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),A()) -> f''#(foldB(triple(s(a),0(),c),b)) f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) foldC#(t,s(n)) -> f#(foldC(t,n),C()) foldC#(t,s(n)) -> foldC#(t,n) f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b) foldB#(t,s(n)) -> f#(foldB(t,n),B()) foldB#(t,s(n)) -> foldB#(t,n) 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) Matrix Interpretation Processor: dimension: 1 interpretation: [f''#](x0) = x0, [f'#](x0, x1) = x0, [foldC#](x0, x1) = x0, [f#](x0, x1) = x0, [foldB#](x0, x1) = x0 + x1, [fold](x0, x1, x2) = x0, [f''](x0) = x0, [triple](x0, x1, x2) = x1, [f'](x0, x1) = x0, [foldC](x0, x1) = x0, [f](x0, x1) = x0, [s](x0) = x0 + 1, [foldB](x0, x1) = x0 + x1, [0] = 0, [C] = 0, [B] = 0, [g](x0) = 0, [A] = 0 orientation: f#(t,x) = t >= t = f'#(t,g(x)) f'#(triple(a,b,c),A()) = b >= b = f''#(foldB(triple(s(a),0(),c),b)) f''#(triple(a,b,c)) = b >= b = foldC#(triple(a,b,0()),c) foldC#(t,s(n)) = t >= t = f#(foldC(t,n),C()) foldC#(t,s(n)) = t >= t = foldC#(t,n) f'#(triple(a,b,c),A()) = b >= b = foldB#(triple(s(a),0(),c),b) foldB#(t,s(n)) = n + t + 1 >= n + t = f#(foldB(t,n),B()) foldB#(t,s(n)) = n + t + 1 >= n + t = foldB#(t,n) f'#(triple(a,b,c),B()) = b >= b = f#(triple(a,b,c),A()) 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 = f(foldB(t,n),B()) foldC(t,0()) = t >= t = t foldC(t,s(n)) = t >= t = f(foldC(t,n),C()) f(t,x) = t >= t = f'(t,g(x)) f'(triple(a,b,c),C()) = b >= b = triple(a,b,s(c)) f'(triple(a,b,c),B()) = b >= b = f(triple(a,b,c),A()) f'(triple(a,b,c),A()) = b >= b = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = b >= b = foldC(triple(a,b,0()),c) fold(t,x,0()) = t >= t = t fold(t,x,s(n)) = t >= t = f(fold(t,x,n),x) problem: DPs: f#(t,x) -> f'#(t,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) foldC#(t,s(n)) -> f#(foldC(t,n),C()) foldC#(t,s(n)) -> foldC#(t,n) f'#(triple(a,b,c),A()) -> foldB#(triple(s(a),0(),c),b) 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) Matrix Interpretation Processor: dimension: 1 interpretation: [f''#](x0) = 1, [f'#](x0, x1) = 1, [foldC#](x0, x1) = 1, [f#](x0, x1) = 1, [foldB#](x0, x1) = 0, [fold](x0, x1, x2) = x0 + 1, [f''](x0) = 1, [triple](x0, x1, x2) = 0, [f'](x0, x1) = 1, [foldC](x0, x1) = x0 + 1, [f](x0, x1) = 1, [s](x0) = 1, [foldB](x0, x1) = x0 + x1, [0] = 0, [C] = 0, [B] = 0, [g](x0) = 1, [A] = 0 orientation: f#(t,x) = 1 >= 1 = f'#(t,g(x)) f'#(triple(a,b,c),A()) = 1 >= 1 = f''#(foldB(triple(s(a),0(),c),b)) f''#(triple(a,b,c)) = 1 >= 1 = foldC#(triple(a,b,0()),c) foldC#(t,s(n)) = 1 >= 1 = f#(foldC(t,n),C()) foldC#(t,s(n)) = 1 >= 1 = foldC#(t,n) f'#(triple(a,b,c),A()) = 1 >= 0 = foldB#(triple(s(a),0(),c),b) f'#(triple(a,b,c),B()) = 1 >= 1 = f#(triple(a,b,c),A()) g(A()) = 1 >= 0 = A() g(B()) = 1 >= 0 = A() g(B()) = 1 >= 0 = B() g(C()) = 1 >= 0 = A() g(C()) = 1 >= 0 = B() g(C()) = 1 >= 0 = C() foldB(t,0()) = t >= t = t foldB(t,s(n)) = t + 1 >= 1 = f(foldB(t,n),B()) foldC(t,0()) = t + 1 >= t = t foldC(t,s(n)) = t + 1 >= 1 = f(foldC(t,n),C()) f(t,x) = 1 >= 1 = f'(t,g(x)) f'(triple(a,b,c),C()) = 1 >= 0 = triple(a,b,s(c)) f'(triple(a,b,c),B()) = 1 >= 1 = f(triple(a,b,c),A()) f'(triple(a,b,c),A()) = 1 >= 1 = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = 1 >= 1 = foldC(triple(a,b,0()),c) fold(t,x,0()) = t + 1 >= t = t fold(t,x,s(n)) = t + 1 >= 1 = f(fold(t,x,n),x) problem: DPs: f#(t,x) -> f'#(t,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) foldC#(t,s(n)) -> f#(foldC(t,n),C()) foldC#(t,s(n)) -> foldC#(t,n) 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) Matrix Interpretation Processor: dimension: 1 interpretation: [f''#](x0) = x0, [f'#](x0, x1) = x0, [foldC#](x0, x1) = x0 + x1, [f#](x0, x1) = x0, [fold](x0, x1, x2) = x0 + x2 + 1, [f''](x0) = x0 + 1, [triple](x0, x1, x2) = x1 + x2, [f'](x0, x1) = x0 + 1, [foldC](x0, x1) = x0 + x1 + 1, [f](x0, x1) = x0 + 1, [s](x0) = x0 + 1, [foldB](x0, x1) = x0 + x1, [0] = 0, [C] = 0, [B] = 0, [g](x0) = 1, [A] = 0 orientation: f#(t,x) = t >= t = f'#(t,g(x)) f'#(triple(a,b,c),A()) = b + c >= 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) foldC#(t,s(n)) = n + t + 1 >= n + t + 1 = f#(foldC(t,n),C()) foldC#(t,s(n)) = n + t + 1 >= n + t = foldC#(t,n) f'#(triple(a,b,c),B()) = b + c >= b + c = f#(triple(a,b,c),A()) g(A()) = 1 >= 0 = A() g(B()) = 1 >= 0 = A() g(B()) = 1 >= 0 = B() g(C()) = 1 >= 0 = A() g(C()) = 1 >= 0 = B() g(C()) = 1 >= 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 + 1 >= t = t foldC(t,s(n)) = n + t + 2 >= n + t + 2 = 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 + 1 = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = b + c + 1 >= b + c + 1 = foldC(triple(a,b,0()),c) fold(t,x,0()) = t + 1 >= t = t fold(t,x,s(n)) = n + t + 2 >= n + t + 2 = f(fold(t,x,n),x) problem: DPs: f#(t,x) -> f'#(t,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) foldC#(t,s(n)) -> f#(foldC(t,n),C()) 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) Matrix Interpretation Processor: dimension: 1 interpretation: [f''#](x0) = x0, [f'#](x0, x1) = x0, [foldC#](x0, x1) = x0 + x1, [f#](x0, x1) = x0, [fold](x0, x1, x2) = x0 + x2, [f''](x0) = x0 + 1, [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) = 1, [A] = 0 orientation: f#(t,x) = t >= t = f'#(t,g(x)) f'#(triple(a,b,c),A()) = b + c >= 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) foldC#(t,s(n)) = n + t + 1 >= n + t = f#(foldC(t,n),C()) f'#(triple(a,b,c),B()) = b + c >= b + c = f#(triple(a,b,c),A()) g(A()) = 1 >= 0 = A() g(B()) = 1 >= 0 = A() g(B()) = 1 >= 0 = B() g(C()) = 1 >= 0 = A() g(C()) = 1 >= 0 = B() g(C()) = 1 >= 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 + 1 = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = b + c + 1 >= b + c = foldC(triple(a,b,0()),c) fold(t,x,0()) = t >= t = t fold(t,x,s(n)) = n + t + 1 >= n + t + 1 = f(fold(t,x,n),x) problem: DPs: f#(t,x) -> f'#(t,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),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) Matrix Interpretation Processor: dimension: 1 interpretation: [f''#](x0) = 0, [f'#](x0, x1) = x0 + 1, [foldC#](x0, x1) = 0, [f#](x0, x1) = x0 + x1 + 1, [fold](x0, x1, x2) = x0, [f''](x0) = 1, [triple](x0, x1, x2) = 1, [f'](x0, x1) = x0, [foldC](x0, x1) = x0, [f](x0, x1) = x0, [s](x0) = 0, [foldB](x0, x1) = x0, [0] = 0, [C] = 0, [B] = 0, [g](x0) = 1, [A] = 0 orientation: f#(t,x) = t + x + 1 >= t + 1 = f'#(t,g(x)) f'#(triple(a,b,c),A()) = 2 >= 0 = f''#(foldB(triple(s(a),0(),c),b)) f''#(triple(a,b,c)) = 0 >= 0 = foldC#(triple(a,b,0()),c) f'#(triple(a,b,c),B()) = 2 >= 2 = f#(triple(a,b,c),A()) g(A()) = 1 >= 0 = A() g(B()) = 1 >= 0 = A() g(B()) = 1 >= 0 = B() g(C()) = 1 >= 0 = A() g(C()) = 1 >= 0 = B() g(C()) = 1 >= 0 = C() foldB(t,0()) = t >= t = t foldB(t,s(n)) = t >= t = f(foldB(t,n),B()) foldC(t,0()) = t >= t = t foldC(t,s(n)) = t >= t = f(foldC(t,n),C()) f(t,x) = t >= t = f'(t,g(x)) f'(triple(a,b,c),C()) = 1 >= 1 = triple(a,b,s(c)) f'(triple(a,b,c),B()) = 1 >= 1 = f(triple(a,b,c),A()) f'(triple(a,b,c),A()) = 1 >= 1 = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = 1 >= 1 = foldC(triple(a,b,0()),c) fold(t,x,0()) = t >= t = t fold(t,x,s(n)) = t >= t = f(fold(t,x,n),x) problem: DPs: f#(t,x) -> f'#(t,g(x)) f''#(triple(a,b,c)) -> foldC#(triple(a,b,0()),c) 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) Subterm Criterion Processor: simple projection: pi(f#) = 0 pi(foldC#) = 1 pi(f'#) = 0 pi(f''#) = 0 problem: DPs: f#(t,x) -> f'#(t,g(x)) 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) Matrix Interpretation Processor: dimension: 1 interpretation: [f'#](x0, x1) = x0 + x1, [f#](x0, x1) = x0 + x1, [fold](x0, x1, x2) = x0, [f''](x0) = 1, [triple](x0, x1, x2) = 1, [f'](x0, x1) = x0, [foldC](x0, x1) = x0, [f](x0, x1) = x0, [s](x0) = 0, [foldB](x0, x1) = x0 + 1, [0] = 0, [C] = 1, [B] = 1, [g](x0) = x0, [A] = 0 orientation: f#(t,x) = t + x >= t + x = f'#(t,g(x)) f'#(triple(a,b,c),B()) = 2 >= 1 = f#(triple(a,b,c),A()) g(A()) = 0 >= 0 = A() g(B()) = 1 >= 0 = A() g(B()) = 1 >= 1 = B() g(C()) = 1 >= 0 = A() g(C()) = 1 >= 1 = B() g(C()) = 1 >= 1 = C() foldB(t,0()) = t + 1 >= t = t foldB(t,s(n)) = t + 1 >= t + 1 = f(foldB(t,n),B()) foldC(t,0()) = t >= t = t foldC(t,s(n)) = t >= t = f(foldC(t,n),C()) f(t,x) = t >= t = f'(t,g(x)) f'(triple(a,b,c),C()) = 1 >= 1 = triple(a,b,s(c)) f'(triple(a,b,c),B()) = 1 >= 1 = f(triple(a,b,c),A()) f'(triple(a,b,c),A()) = 1 >= 1 = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = 1 >= 1 = foldC(triple(a,b,0()),c) fold(t,x,0()) = t >= t = t fold(t,x,s(n)) = t >= t = f(fold(t,x,n),x) problem: DPs: 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) Matrix Interpretation Processor: dimension: 1 interpretation: [f'#](x0, x1) = 0, [f#](x0, x1) = 1, [fold](x0, x1, x2) = x0, [f''](x0) = 0, [triple](x0, x1, x2) = 0, [f'](x0, x1) = x0, [foldC](x0, x1) = x0, [f](x0, x1) = x0, [s](x0) = 0, [foldB](x0, x1) = x0, [0] = 0, [C] = 0, [B] = 0, [g](x0) = 0, [A] = 0 orientation: f#(t,x) = 1 >= 0 = f'#(t,g(x)) 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)) = t >= t = f(foldB(t,n),B()) foldC(t,0()) = t >= t = t foldC(t,s(n)) = t >= t = f(foldC(t,n),C()) f(t,x) = t >= t = f'(t,g(x)) f'(triple(a,b,c),C()) = 0 >= 0 = triple(a,b,s(c)) f'(triple(a,b,c),B()) = 0 >= 0 = f(triple(a,b,c),A()) f'(triple(a,b,c),A()) = 0 >= 0 = f''(foldB(triple(s(a),0(),c),b)) f''(triple(a,b,c)) = 0 >= 0 = foldC(triple(a,b,0()),c) fold(t,x,0()) = t >= t = t fold(t,x,s(n)) = t >= t = f(fold(t,x,n),x) 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