YES Problem 1: (VAR v_NonEmpty:S x1:S) (RULES f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ) Problem 1: Dependency Pairs Processor: -> Pairs: F(s(x1:S)) -> G(p(s(s(x1:S)))) F(s(x1:S)) -> P(s(g(p(s(s(x1:S)))))) F(s(x1:S)) -> P(s(s(x1:S))) G(s(x1:S)) -> J(s(p(s(p(s(x1:S)))))) G(s(x1:S)) -> P(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) G(s(x1:S)) -> P(s(p(s(x1:S)))) G(s(x1:S)) -> P(s(s(s(j(s(p(s(p(s(x1:S)))))))))) G(s(x1:S)) -> P(s(x1:S)) HALF(0(x1:S)) -> HALF(p(s(p(s(x1:S))))) HALF(0(x1:S)) -> P(s(p(s(x1:S)))) HALF(0(x1:S)) -> P(s(x1:S)) HALF(s(s(x1:S))) -> HALF(p(p(s(s(x1:S))))) HALF(s(s(x1:S))) -> P(p(s(s(x1:S)))) HALF(s(s(x1:S))) -> P(s(s(x1:S))) J(s(x1:S)) -> F(p(s(p(p(s(x1:S)))))) J(s(x1:S)) -> P(p(s(x1:S))) J(s(x1:S)) -> P(s(f(p(s(p(p(s(x1:S)))))))) J(s(x1:S)) -> P(s(p(p(s(x1:S))))) J(s(x1:S)) -> P(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) J(s(x1:S)) -> P(s(x1:S)) P(p(s(x1:S))) -> P(x1:S) P(0(x1:S)) -> P(x1:S) RD(0(x1:S)) -> RD(x1:S) -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) Problem 1: SCC Processor: -> Pairs: F(s(x1:S)) -> G(p(s(s(x1:S)))) F(s(x1:S)) -> P(s(g(p(s(s(x1:S)))))) F(s(x1:S)) -> P(s(s(x1:S))) G(s(x1:S)) -> J(s(p(s(p(s(x1:S)))))) G(s(x1:S)) -> P(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) G(s(x1:S)) -> P(s(p(s(x1:S)))) G(s(x1:S)) -> P(s(s(s(j(s(p(s(p(s(x1:S)))))))))) G(s(x1:S)) -> P(s(x1:S)) HALF(0(x1:S)) -> HALF(p(s(p(s(x1:S))))) HALF(0(x1:S)) -> P(s(p(s(x1:S)))) HALF(0(x1:S)) -> P(s(x1:S)) HALF(s(s(x1:S))) -> HALF(p(p(s(s(x1:S))))) HALF(s(s(x1:S))) -> P(p(s(s(x1:S)))) HALF(s(s(x1:S))) -> P(s(s(x1:S))) J(s(x1:S)) -> F(p(s(p(p(s(x1:S)))))) J(s(x1:S)) -> P(p(s(x1:S))) J(s(x1:S)) -> P(s(f(p(s(p(p(s(x1:S)))))))) J(s(x1:S)) -> P(s(p(p(s(x1:S))))) J(s(x1:S)) -> P(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) J(s(x1:S)) -> P(s(x1:S)) P(p(s(x1:S))) -> P(x1:S) P(0(x1:S)) -> P(x1:S) RD(0(x1:S)) -> RD(x1:S) -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: RD(0(x1:S)) -> RD(x1:S) ->->-> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->->Cycle: ->->-> Pairs: P(p(s(x1:S))) -> P(x1:S) P(0(x1:S)) -> P(x1:S) ->->-> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->->Cycle: ->->-> Pairs: HALF(0(x1:S)) -> HALF(p(s(p(s(x1:S))))) HALF(s(s(x1:S))) -> HALF(p(p(s(s(x1:S))))) ->->-> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->->Cycle: ->->-> Pairs: F(s(x1:S)) -> G(p(s(s(x1:S)))) G(s(x1:S)) -> J(s(p(s(p(s(x1:S)))))) J(s(x1:S)) -> F(p(s(p(p(s(x1:S)))))) ->->-> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) The problem is decomposed in 4 subproblems. Problem 1.1: Subterm Processor: -> Pairs: RD(0(x1:S)) -> RD(x1:S) -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->Projection: pi(RD) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: P(p(s(x1:S))) -> P(x1:S) P(0(x1:S)) -> P(x1:S) -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->Projection: pi(P) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Reduction Pair Processor: -> Pairs: HALF(0(x1:S)) -> HALF(p(s(p(s(x1:S))))) HALF(s(s(x1:S))) -> HALF(p(p(s(s(x1:S))))) -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) -> Usable rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [p](X) = X [0](X) = X + 1 [s](X) = X [HALF](X) = X Problem 1.3: SCC Processor: -> Pairs: HALF(s(s(x1:S))) -> HALF(p(p(s(s(x1:S))))) -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: HALF(s(s(x1:S))) -> HALF(p(p(s(s(x1:S))))) ->->-> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) Problem 1.3: Reduction Pair Processor: -> Pairs: HALF(s(s(x1:S))) -> HALF(p(p(s(s(x1:S))))) -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) -> Usable rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [p](X) = 1/2.X + 1 [0](X) = 2 [s](X) = 2.X + 2 [HALF](X) = 2.X Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Reduction Pair Processor: -> Pairs: F(s(x1:S)) -> G(p(s(s(x1:S)))) G(s(x1:S)) -> J(s(p(s(p(s(x1:S)))))) J(s(x1:S)) -> F(p(s(p(p(s(x1:S)))))) -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) -> Usable rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 4 ->Interpretation: [p](X) = 1/3.X [0](X) = 0 [s](X) = 3.X + 3/2 [F](X) = 4.X + 1/4 [G](X) = X + 4 [J](X) = 2/3.X + 2 Problem 1.4: SCC Processor: -> Pairs: G(s(x1:S)) -> J(s(p(s(p(s(x1:S)))))) J(s(x1:S)) -> F(p(s(p(p(s(x1:S)))))) -> Rules: f(s(x1:S)) -> p(s(g(p(s(s(x1:S)))))) g(s(x1:S)) -> p(p(s(s(s(j(s(p(s(p(s(x1:S))))))))))) half(0(x1:S)) -> 0(s(s(half(p(s(p(s(x1:S)))))))) half(s(s(x1:S))) -> s(half(p(p(s(s(x1:S)))))) j(s(x1:S)) -> p(s(s(p(s(f(p(s(p(p(s(x1:S))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(p(x1:S)))) p(s(x1:S)) -> x1:S rd(0(x1:S)) -> 0(s(0(0(0(0(s(0(rd(x1:S))))))))) ->Strongly Connected Components: There is no strongly connected component The problem is finite.