YES Problem 1: (VAR v_NonEmpty:S x1:S) (RULES p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S q(0(x1:S)) -> p(p(s(s(0(s(s(s(s(x1:S))))))))) q(s(x1:S)) -> p(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) r(0(x1:S)) -> p(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) r(s(x1:S)) -> p(s(p(s(s(q(p(s(p(s(x1:S)))))))))) ) Problem 1: Dependency Pairs Processor: -> Pairs: P(p(s(x1:S))) -> P(x1:S) Q(0(x1:S)) -> P(p(s(s(0(s(s(s(s(x1:S))))))))) Q(0(x1:S)) -> P(s(s(0(s(s(s(s(x1:S)))))))) Q(s(x1:S)) -> P(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) Q(s(x1:S)) -> P(p(s(s(x1:S)))) Q(s(x1:S)) -> P(s(s(s(s(s(s(r(p(p(s(s(x1:S)))))))))))) Q(s(x1:S)) -> P(s(s(x1:S))) Q(s(x1:S)) -> R(p(p(s(s(x1:S))))) R(0(x1:S)) -> P(p(p(s(s(s(x1:S)))))) R(0(x1:S)) -> P(p(s(s(s(x1:S))))) R(0(x1:S)) -> P(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) R(0(x1:S)) -> P(s(0(p(p(p(s(s(s(x1:S))))))))) R(0(x1:S)) -> P(s(s(s(x1:S)))) R(s(x1:S)) -> P(s(p(s(s(q(p(s(p(s(x1:S)))))))))) R(s(x1:S)) -> P(s(p(s(x1:S)))) R(s(x1:S)) -> P(s(s(q(p(s(p(s(x1:S)))))))) R(s(x1:S)) -> P(s(x1:S)) R(s(x1:S)) -> Q(p(s(p(s(x1:S))))) -> Rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S q(0(x1:S)) -> p(p(s(s(0(s(s(s(s(x1:S))))))))) q(s(x1:S)) -> p(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) r(0(x1:S)) -> p(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) r(s(x1:S)) -> p(s(p(s(s(q(p(s(p(s(x1:S)))))))))) Problem 1: SCC Processor: -> Pairs: P(p(s(x1:S))) -> P(x1:S) Q(0(x1:S)) -> P(p(s(s(0(s(s(s(s(x1:S))))))))) Q(0(x1:S)) -> P(s(s(0(s(s(s(s(x1:S)))))))) Q(s(x1:S)) -> P(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) Q(s(x1:S)) -> P(p(s(s(x1:S)))) Q(s(x1:S)) -> P(s(s(s(s(s(s(r(p(p(s(s(x1:S)))))))))))) Q(s(x1:S)) -> P(s(s(x1:S))) Q(s(x1:S)) -> R(p(p(s(s(x1:S))))) R(0(x1:S)) -> P(p(p(s(s(s(x1:S)))))) R(0(x1:S)) -> P(p(s(s(s(x1:S))))) R(0(x1:S)) -> P(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) R(0(x1:S)) -> P(s(0(p(p(p(s(s(s(x1:S))))))))) R(0(x1:S)) -> P(s(s(s(x1:S)))) R(s(x1:S)) -> P(s(p(s(s(q(p(s(p(s(x1:S)))))))))) R(s(x1:S)) -> P(s(p(s(x1:S)))) R(s(x1:S)) -> P(s(s(q(p(s(p(s(x1:S)))))))) R(s(x1:S)) -> P(s(x1:S)) R(s(x1:S)) -> Q(p(s(p(s(x1:S))))) -> Rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S q(0(x1:S)) -> p(p(s(s(0(s(s(s(s(x1:S))))))))) q(s(x1:S)) -> p(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) r(0(x1:S)) -> p(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) r(s(x1:S)) -> p(s(p(s(s(q(p(s(p(s(x1:S)))))))))) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: P(p(s(x1:S))) -> P(x1:S) ->->-> Rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S q(0(x1:S)) -> p(p(s(s(0(s(s(s(s(x1:S))))))))) q(s(x1:S)) -> p(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) r(0(x1:S)) -> p(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) r(s(x1:S)) -> p(s(p(s(s(q(p(s(p(s(x1:S)))))))))) ->->Cycle: ->->-> Pairs: Q(s(x1:S)) -> R(p(p(s(s(x1:S))))) R(s(x1:S)) -> Q(p(s(p(s(x1:S))))) ->->-> Rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S q(0(x1:S)) -> p(p(s(s(0(s(s(s(s(x1:S))))))))) q(s(x1:S)) -> p(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) r(0(x1:S)) -> p(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) r(s(x1:S)) -> p(s(p(s(s(q(p(s(p(s(x1:S)))))))))) The problem is decomposed in 2 subproblems. Problem 1.1: Subterm Processor: -> Pairs: P(p(s(x1:S))) -> P(x1:S) -> Rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S q(0(x1:S)) -> p(p(s(s(0(s(s(s(s(x1:S))))))))) q(s(x1:S)) -> p(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) r(0(x1:S)) -> p(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) r(s(x1:S)) -> p(s(p(s(s(q(p(s(p(s(x1:S)))))))))) ->Projection: pi(P) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S q(0(x1:S)) -> p(p(s(s(0(s(s(s(s(x1:S))))))))) q(s(x1:S)) -> p(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) r(0(x1:S)) -> p(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) r(s(x1:S)) -> p(s(p(s(s(q(p(s(p(s(x1:S)))))))))) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pair Processor: -> Pairs: Q(s(x1:S)) -> R(p(p(s(s(x1:S))))) R(s(x1:S)) -> Q(p(s(p(s(x1:S))))) -> Rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S q(0(x1:S)) -> p(p(s(s(0(s(s(s(s(x1:S))))))))) q(s(x1:S)) -> p(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) r(0(x1:S)) -> p(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) r(s(x1:S)) -> p(s(p(s(s(q(p(s(p(s(x1:S)))))))))) -> Usable rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [p](X) = 1/2.X [0](X) = 0 [s](X) = 2.X + 1 [Q](X) = 1/2.X + 1/2 [R](X) = X Problem 1.2: SCC Processor: -> Pairs: R(s(x1:S)) -> Q(p(s(p(s(x1:S))))) -> Rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(x1:S)))) p(s(x1:S)) -> x1:S q(0(x1:S)) -> p(p(s(s(0(s(s(s(s(x1:S))))))))) q(s(x1:S)) -> p(p(s(s(s(s(s(s(r(p(p(s(s(x1:S))))))))))))) r(0(x1:S)) -> p(s(p(s(0(p(p(p(s(s(s(x1:S))))))))))) r(s(x1:S)) -> p(s(p(s(s(q(p(s(p(s(x1:S)))))))))) ->Strongly Connected Components: There is no strongly connected component The problem is finite.