YES Problem 1: (VAR v_NonEmpty:S x1:S) (RULES i(0(x1:S)) -> p(s(p(s(0(p(s(p(s(x1:S))))))))) i(s(x1:S)) -> p(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) j(0(x1:S)) -> p(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) j(s(x1:S)) -> s(s(s(s(p(p(s(s(i(p(s(p(s(x1:S))))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1:S)) -> x1:S ) Problem 1: Dependency Pairs Processor: -> Pairs: I(0(x1:S)) -> P(s(p(s(0(p(s(p(s(x1:S))))))))) I(0(x1:S)) -> P(s(p(s(x1:S)))) I(0(x1:S)) -> P(s(0(p(s(p(s(x1:S))))))) I(0(x1:S)) -> P(s(x1:S)) I(s(x1:S)) -> J(p(s(p(s(p(p(p(p(s(s(s(s(x1:S))))))))))))) I(s(x1:S)) -> P(p(p(p(s(s(s(s(x1:S)))))))) I(s(x1:S)) -> P(p(p(s(s(s(s(x1:S))))))) I(s(x1:S)) -> P(p(s(s(s(s(x1:S)))))) I(s(x1:S)) -> P(s(p(p(p(p(s(s(s(s(x1:S)))))))))) I(s(x1:S)) -> P(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))) I(s(x1:S)) -> P(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) I(s(x1:S)) -> P(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))) I(s(x1:S)) -> P(s(s(s(s(x1:S))))) J(0(x1:S)) -> P(p(s(s(0(p(s(p(s(x1:S))))))))) J(0(x1:S)) -> P(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) J(0(x1:S)) -> P(s(p(s(x1:S)))) J(0(x1:S)) -> P(s(s(0(p(s(p(s(x1:S)))))))) J(0(x1:S)) -> P(s(x1:S)) J(s(x1:S)) -> I(p(s(p(s(x1:S))))) J(s(x1:S)) -> P(p(s(s(i(p(s(p(s(x1:S))))))))) J(s(x1:S)) -> P(s(p(s(x1:S)))) J(s(x1:S)) -> P(s(s(i(p(s(p(s(x1:S)))))))) J(s(x1:S)) -> P(s(x1:S)) P(p(s(x1:S))) -> P(x1:S) -> Rules: i(0(x1:S)) -> p(s(p(s(0(p(s(p(s(x1:S))))))))) i(s(x1:S)) -> p(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) j(0(x1:S)) -> p(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) j(s(x1:S)) -> s(s(s(s(p(p(s(s(i(p(s(p(s(x1:S))))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1:S)) -> x1:S Problem 1: SCC Processor: -> Pairs: I(0(x1:S)) -> P(s(p(s(0(p(s(p(s(x1:S))))))))) I(0(x1:S)) -> P(s(p(s(x1:S)))) I(0(x1:S)) -> P(s(0(p(s(p(s(x1:S))))))) I(0(x1:S)) -> P(s(x1:S)) I(s(x1:S)) -> J(p(s(p(s(p(p(p(p(s(s(s(s(x1:S))))))))))))) I(s(x1:S)) -> P(p(p(p(s(s(s(s(x1:S)))))))) I(s(x1:S)) -> P(p(p(s(s(s(s(x1:S))))))) I(s(x1:S)) -> P(p(s(s(s(s(x1:S)))))) I(s(x1:S)) -> P(s(p(p(p(p(s(s(s(s(x1:S)))))))))) I(s(x1:S)) -> P(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))) I(s(x1:S)) -> P(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) I(s(x1:S)) -> P(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))) I(s(x1:S)) -> P(s(s(s(s(x1:S))))) J(0(x1:S)) -> P(p(s(s(0(p(s(p(s(x1:S))))))))) J(0(x1:S)) -> P(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) J(0(x1:S)) -> P(s(p(s(x1:S)))) J(0(x1:S)) -> P(s(s(0(p(s(p(s(x1:S)))))))) J(0(x1:S)) -> P(s(x1:S)) J(s(x1:S)) -> I(p(s(p(s(x1:S))))) J(s(x1:S)) -> P(p(s(s(i(p(s(p(s(x1:S))))))))) J(s(x1:S)) -> P(s(p(s(x1:S)))) J(s(x1:S)) -> P(s(s(i(p(s(p(s(x1:S)))))))) J(s(x1:S)) -> P(s(x1:S)) P(p(s(x1:S))) -> P(x1:S) -> Rules: i(0(x1:S)) -> p(s(p(s(0(p(s(p(s(x1:S))))))))) i(s(x1:S)) -> p(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) j(0(x1:S)) -> p(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) j(s(x1:S)) -> s(s(s(s(p(p(s(s(i(p(s(p(s(x1:S))))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1:S)) -> x1:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: P(p(s(x1:S))) -> P(x1:S) ->->-> Rules: i(0(x1:S)) -> p(s(p(s(0(p(s(p(s(x1:S))))))))) i(s(x1:S)) -> p(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) j(0(x1:S)) -> p(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) j(s(x1:S)) -> s(s(s(s(p(p(s(s(i(p(s(p(s(x1:S))))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1:S)) -> x1:S ->->Cycle: ->->-> Pairs: I(s(x1:S)) -> J(p(s(p(s(p(p(p(p(s(s(s(s(x1:S))))))))))))) J(s(x1:S)) -> I(p(s(p(s(x1:S))))) ->->-> Rules: i(0(x1:S)) -> p(s(p(s(0(p(s(p(s(x1:S))))))))) i(s(x1:S)) -> p(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) j(0(x1:S)) -> p(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) j(s(x1:S)) -> s(s(s(s(p(p(s(s(i(p(s(p(s(x1:S))))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1: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: i(0(x1:S)) -> p(s(p(s(0(p(s(p(s(x1:S))))))))) i(s(x1:S)) -> p(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) j(0(x1:S)) -> p(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) j(s(x1:S)) -> s(s(s(s(p(p(s(s(i(p(s(p(s(x1:S))))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1:S)) -> x1:S ->Projection: pi(P) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: i(0(x1:S)) -> p(s(p(s(0(p(s(p(s(x1:S))))))))) i(s(x1:S)) -> p(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) j(0(x1:S)) -> p(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) j(s(x1:S)) -> s(s(s(s(p(p(s(s(i(p(s(p(s(x1:S))))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1:S)) -> x1:S ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pair Processor: -> Pairs: I(s(x1:S)) -> J(p(s(p(s(p(p(p(p(s(s(s(s(x1:S))))))))))))) J(s(x1:S)) -> I(p(s(p(s(x1:S))))) -> Rules: i(0(x1:S)) -> p(s(p(s(0(p(s(p(s(x1:S))))))))) i(s(x1:S)) -> p(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) j(0(x1:S)) -> p(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) j(s(x1:S)) -> s(s(s(s(p(p(s(s(i(p(s(p(s(x1:S))))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1:S)) -> x1:S -> Usable rules: p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1:S)) -> x1:S ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 4 ->Interpretation: [p](X) = 1/4.X [0](X) = 0 [s](X) = 4.X + 1/4 [I](X) = 3.X + 1 [J](X) = 2.X + 4/3 Problem 1.2: SCC Processor: -> Pairs: J(s(x1:S)) -> I(p(s(p(s(x1:S))))) -> Rules: i(0(x1:S)) -> p(s(p(s(0(p(s(p(s(x1:S))))))))) i(s(x1:S)) -> p(s(p(s(s(j(p(s(p(s(p(p(p(p(s(s(s(s(x1:S)))))))))))))))))) j(0(x1:S)) -> p(s(p(p(s(s(0(p(s(p(s(x1:S))))))))))) j(s(x1:S)) -> s(s(s(s(p(p(s(s(i(p(s(p(s(x1:S))))))))))))) p(p(s(x1:S))) -> p(x1:S) p(0(x1:S)) -> 0(s(s(s(s(s(s(s(s(x1:S))))))))) p(s(x1:S)) -> x1:S ->Strongly Connected Components: There is no strongly connected component The problem is finite.