/export/starexec/sandbox2/solver/bin/starexec_run_default /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR x y z) (RULES add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ) Problem 1: Innermost Equivalent Processor: -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x -> The term rewriting system is non-overlaping or locally confluent overlay system. Therefore, innermost termination implies termination. Problem 1: Dependency Pairs Processor: -> Pairs: ADD(s(x),y) -> ADD(x,y) COND1(true,x,y,z) -> COND2(gr(x,0),x,y,z) COND1(true,x,y,z) -> GR(x,0) COND2(false,x,y,z) -> COND3(gr(y,0),x,y,z) COND2(false,x,y,z) -> GR(y,0) COND2(true,x,y,z) -> ADD(x,y) COND2(true,x,y,z) -> COND1(gr(add(x,y),z),p(x),y,z) COND2(true,x,y,z) -> GR(add(x,y),z) COND2(true,x,y,z) -> P(x) COND3(false,x,y,z) -> ADD(x,y) COND3(false,x,y,z) -> COND1(gr(add(x,y),z),x,y,z) COND3(false,x,y,z) -> GR(add(x,y),z) COND3(true,x,y,z) -> ADD(x,y) COND3(true,x,y,z) -> COND1(gr(add(x,y),z),x,p(y),z) COND3(true,x,y,z) -> GR(add(x,y),z) COND3(true,x,y,z) -> P(y) GR(s(x),s(y)) -> GR(x,y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x Problem 1: SCC Processor: -> Pairs: ADD(s(x),y) -> ADD(x,y) COND1(true,x,y,z) -> COND2(gr(x,0),x,y,z) COND1(true,x,y,z) -> GR(x,0) COND2(false,x,y,z) -> COND3(gr(y,0),x,y,z) COND2(false,x,y,z) -> GR(y,0) COND2(true,x,y,z) -> ADD(x,y) COND2(true,x,y,z) -> COND1(gr(add(x,y),z),p(x),y,z) COND2(true,x,y,z) -> GR(add(x,y),z) COND2(true,x,y,z) -> P(x) COND3(false,x,y,z) -> ADD(x,y) COND3(false,x,y,z) -> COND1(gr(add(x,y),z),x,y,z) COND3(false,x,y,z) -> GR(add(x,y),z) COND3(true,x,y,z) -> ADD(x,y) COND3(true,x,y,z) -> COND1(gr(add(x,y),z),x,p(y),z) COND3(true,x,y,z) -> GR(add(x,y),z) COND3(true,x,y,z) -> P(y) GR(s(x),s(y)) -> GR(x,y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: GR(s(x),s(y)) -> GR(x,y) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->->Cycle: ->->-> Pairs: ADD(s(x),y) -> ADD(x,y) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->->Cycle: ->->-> Pairs: COND1(true,x,y,z) -> COND2(gr(x,0),x,y,z) COND2(false,x,y,z) -> COND3(gr(y,0),x,y,z) COND2(true,x,y,z) -> COND1(gr(add(x,y),z),p(x),y,z) COND3(false,x,y,z) -> COND1(gr(add(x,y),z),x,y,z) COND3(true,x,y,z) -> COND1(gr(add(x,y),z),x,p(y),z) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x The problem is decomposed in 3 subproblems. Problem 1.1: Subterm Processor: -> Pairs: GR(s(x),s(y)) -> GR(x,y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Projection: pi(GR) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: ADD(s(x),y) -> ADD(x,y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Projection: pi(ADD) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Narrowing Processor: -> Pairs: COND1(true,x,y,z) -> COND2(gr(x,0),x,y,z) COND2(false,x,y,z) -> COND3(gr(y,0),x,y,z) COND2(true,x,y,z) -> COND1(gr(add(x,y),z),p(x),y,z) COND3(false,x,y,z) -> COND1(gr(add(x,y),z),x,y,z) COND3(true,x,y,z) -> COND1(gr(add(x,y),z),x,p(y),z) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Narrowed Pairs: ->->Original Pair: COND1(true,x,y,z) -> COND2(gr(x,0),x,y,z) ->-> Narrowed pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) ->->Original Pair: COND2(false,x,y,z) -> COND3(gr(y,0),x,y,z) ->-> Narrowed pairs: COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) ->->Original Pair: COND2(true,x,y,z) -> COND1(gr(add(x,y),z),p(x),y,z) ->-> Narrowed pairs: COND2(true,0,x,x11) -> COND1(gr(x,x11),p(0),x,x11) COND2(true,0,x10,x11) -> COND1(gr(add(0,x10),x11),0,x10,x11) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND2(true,s(x),x10,x11) -> COND1(gr(add(s(x),x10),x11),x,x10,x11) ->->Original Pair: COND3(false,x,y,z) -> COND1(gr(add(x,y),z),x,y,z) ->-> Narrowed pairs: COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) ->->Original Pair: COND3(true,x,y,z) -> COND1(gr(add(x,y),z),x,p(y),z) ->-> Narrowed pairs: COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) COND3(true,x15,0,x17) -> COND1(gr(add(x15,0),x17),x15,0,x17) COND3(true,x15,s(x),x17) -> COND1(gr(add(x15,s(x)),x17),x15,x,x17) Problem 1.3: SCC Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,0,x,x11) -> COND1(gr(x,x11),p(0),x,x11) COND2(true,0,x10,x11) -> COND1(gr(add(0,x10),x11),0,x10,x11) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND2(true,s(x),x10,x11) -> COND1(gr(add(s(x),x10),x11),x,x10,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) COND3(true,x15,0,x17) -> COND1(gr(add(x15,0),x17),x15,0,x17) COND3(true,x15,s(x),x17) -> COND1(gr(add(x15,s(x)),x17),x15,x,x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND2(true,s(x),x10,x11) -> COND1(gr(add(s(x),x10),x11),x,x10,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) COND3(true,x15,s(x),x17) -> COND1(gr(add(x15,s(x)),x17),x15,x,x17) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x Problem 1.3: Reduction Pairs Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND2(true,s(x),x10,x11) -> COND1(gr(add(s(x),x10),x11),x,x10,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) COND3(true,x15,s(x),x17) -> COND1(gr(add(x15,s(x)),x17),x15,x,x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [add](X1,X2) = X1 + 2.X2 + 2 [gr](X1,X2) = 2 [p](X) = X [0] = 2 [false] = 2 [s](X) = X + 1 [true] = 2 [COND1](X1,X2,X3,X4) = 2.X1 + 2.X2 + X3 + 2 [COND2](X1,X2,X3,X4) = 2.X1 + 2.X2 + X3 + 2 [COND3](X1,X2,X3,X4) = 2.X1 + 2.X2 + X3 + 2 Problem 1.3: SCC Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) COND3(true,x15,s(x),x17) -> COND1(gr(add(x15,s(x)),x17),x15,x,x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) COND3(true,x15,s(x),x17) -> COND1(gr(add(x15,s(x)),x17),x15,x,x17) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x Problem 1.3: Reduction Pairs Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) COND3(true,x15,s(x),x17) -> COND1(gr(add(x15,s(x)),x17),x15,x,x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [add](X1,X2) = 2.X1 + 2.X2 + 2 [gr](X1,X2) = 2 [p](X) = X [0] = 2 [false] = 2 [s](X) = X + 2 [true] = 2 [COND1](X1,X2,X3,X4) = X1 + 2.X2 + 2.X3 + 2.X4 + 2 [COND2](X1,X2,X3,X4) = X1 + 2.X2 + 2.X3 + 2.X4 + 2 [COND3](X1,X2,X3,X4) = X1 + 2.X2 + 2.X3 + 2.X4 + 2 Problem 1.3: SCC Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x Problem 1.3: Reduction Pairs Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(false,s(x),y,x14) -> COND1(gr(s(add(x,y)),x14),s(x),y,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [add](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2 [gr](X1,X2) = X1.X2 + 2.X1 + 2 [p](X) = 2.X.X [0] = 0 [false] = 2 [s](X) = 2.X + 2 [true] = 0 [COND1](X1,X2,X3,X4) = X4 + 1 [COND2](X1,X2,X3,X4) = 2.X1.X2.X3.X4 + 2.X1.X2.X4 + 2.X1.X2 + X4 + 1 [COND3](X1,X2,X3,X4) = X1.X2.X4 + 2.X1.X3.X4 + X2.X3.X4 + X1.X2 + 2.X1.X3 + 2.X2.X4 + 2.X2 + X4 + 1 Problem 1.3: SCC Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x Problem 1.3: Reduction Pairs Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) COND3(true,s(x),y,x17) -> COND1(gr(s(add(x,y)),x17),s(x),p(y),x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [add](X1,X2) = 2.X1.X2 + 2.X1 + 2.X2 + 2 [gr](X1,X2) = 2.X1 + 2 [p](X) = 2.X.X [0] = 0 [false] = 2 [s](X) = 2.X + 2 [true] = 0 [COND1](X1,X2,X3,X4) = 2 [COND2](X1,X2,X3,X4) = 2.X1.X2.X3.X4 + 2.X1.X2.X3 + 2.X1.X2.X4 + 2.X1.X2 + 2 [COND3](X1,X2,X3,X4) = 2.X1.X2.X4 + 2.X1.X3.X4 + 2.X2.X3.X4 + 2.X1.X3 + 2.X2.X3 + 2.X2 + 2 Problem 1.3: SCC Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->->Cycle: ->->-> Pairs: COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x The problem is decomposed in 2 subproblems. Problem 1.3.1: Reduction Pairs Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND2(false,x6,s(x),x8) -> COND3(true,x6,s(x),x8) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x -> Usable rules: gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Interpretation type: Simple mixed ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = 1/2 [p](X) = 1/2.X [0] = 0 [false] = 1/2 [s](X) = 2.X + 2 [true] = 0 [COND1](X1,X2,X3,X4) = X1.X3.X4 + 2.X1.X2 + 2.X2.X3 + X3.X4 + X2 + X3 + X4 [COND2](X1,X2,X3,X4) = 2.X1.X2.X3.X4 + 2.X1.X2.X3 + 2.X1.X2.X4 + X1.X3.X4 + 2.X2.X3.X4 + 2.X1.X2 + X1.X4 + 2.X2.X3 + 2.X2.X4 + 1/2.X3.X4 + 2.X2 + X3 + 1/2.X4 [COND3](X1,X2,X3,X4) = X1.X2.X3 + 2.X1.X2.X4 + X1.X3.X4 + X1.X2 + 2.X1.X3 + 2.X2.X3 + 2.X2.X4 + X3.X4 + 1/2.X3 + X4 Problem 1.3.1: SCC Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) COND3(true,0,x,x17) -> COND1(gr(x,x17),0,p(x),x17) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x Problem 1.3.1: Reduction Pairs Processor: -> Pairs: COND1(true,0,x4,x5) -> COND2(false,0,x4,x5) COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x -> Usable rules: gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = X1 [0] = 1 [false] = 1 [s](X) = 2.X + 2 [true] = 2 [COND1](X1,X2,X3,X4) = X1 + 2.X2 + X3 + 2 [COND2](X1,X2,X3,X4) = X1 + 2.X2 + X3 + 2 [COND3](X1,X2,X3,X4) = 2.X2 + 2.X3 + 2 Problem 1.3.1: SCC Processor: -> Pairs: COND2(false,x6,0,x8) -> COND3(false,x6,0,x8) COND3(false,0,x,x14) -> COND1(gr(x,x14),0,x,x14) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3.2: Reduction Pairs Processor: -> Pairs: COND1(true,s(x),x4,x5) -> COND2(true,s(x),x4,x5) COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Interpretation type: Simple mixed ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [add](X1,X2) = 1/2.X1.X2 + 2.X1 + X2 [gr](X1,X2) = X2 + 1 [p](X) = 1/2.X [0] = 0 [false] = 0 [s](X) = 2.X + 2 [true] = 1 [COND1](X1,X2,X3,X4) = X2.X3.X4 + X1.X2 + 2.X2.X3 + 2.X2.X4 + X3.X4 + X1 + 1/2.X2 + X3 + 2.X4 + 1/2 [COND2](X1,X2,X3,X4) = X1.X2.X3.X4 + 2.X1.X2.X3 + 1/2.X1.X2.X4 + X1.X2 + 2.X1.X4 + X2.X4 + 1/2.X1 + X3 + X4 + 1 Problem 1.3.2: SCC Processor: -> Pairs: COND2(true,s(x),y,x11) -> COND1(gr(s(add(x,y)),x11),p(s(x)),y,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y,z) -> cond2(gr(x,0),x,y,z) cond2(false,x,y,z) -> cond3(gr(y,0),x,y,z) cond2(true,x,y,z) -> cond1(gr(add(x,y),z),p(x),y,z) cond3(false,x,y,z) -> cond1(gr(add(x,y),z),x,y,z) cond3(true,x,y,z) -> cond1(gr(add(x,y),z),x,p(y),z) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: There is no strongly connected component The problem is finite.