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