/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR x y) (RULES add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ) Problem 1: Innermost Equivalent Processor: -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 -> 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) -> COND2(gr(x,y),x,y) COND1(true,x,y) -> GR(x,y) COND2(false,x,y) -> COND3(eq(x,y),x,y) COND2(false,x,y) -> EQ(x,y) COND2(true,x,y) -> ADD(x,y) COND2(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) COND2(true,x,y) -> GR(add(x,y),0) COND2(true,x,y) -> P(x) COND3(false,x,y) -> ADD(x,y) COND3(false,x,y) -> COND1(gr(add(x,y),0),x,p(y)) COND3(false,x,y) -> GR(add(x,y),0) COND3(false,x,y) -> P(y) COND3(true,x,y) -> ADD(x,y) COND3(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) COND3(true,x,y) -> GR(add(x,y),0) COND3(true,x,y) -> P(x) EQ(s(x),s(y)) -> EQ(x,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) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 Problem 1: SCC Processor: -> Pairs: ADD(s(x),y) -> ADD(x,y) COND1(true,x,y) -> COND2(gr(x,y),x,y) COND1(true,x,y) -> GR(x,y) COND2(false,x,y) -> COND3(eq(x,y),x,y) COND2(false,x,y) -> EQ(x,y) COND2(true,x,y) -> ADD(x,y) COND2(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) COND2(true,x,y) -> GR(add(x,y),0) COND2(true,x,y) -> P(x) COND3(false,x,y) -> ADD(x,y) COND3(false,x,y) -> COND1(gr(add(x,y),0),x,p(y)) COND3(false,x,y) -> GR(add(x,y),0) COND3(false,x,y) -> P(y) COND3(true,x,y) -> ADD(x,y) COND3(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) COND3(true,x,y) -> GR(add(x,y),0) COND3(true,x,y) -> P(x) EQ(s(x),s(y)) -> EQ(x,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) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->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) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->->Cycle: ->->-> Pairs: EQ(s(x),s(y)) -> EQ(x,y) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->->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) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->->Cycle: ->->-> Pairs: COND1(true,x,y) -> COND2(gr(x,y),x,y) COND2(false,x,y) -> COND3(eq(x,y),x,y) COND2(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) COND3(false,x,y) -> COND1(gr(add(x,y),0),x,p(y)) COND3(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 The problem is decomposed in 4 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) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->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) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Subterm Processor: -> Pairs: EQ(s(x),s(y)) -> EQ(x,y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Projection: pi(EQ) = 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) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: 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) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Projection: pi(ADD) = 1 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Narrowing Processor: -> Pairs: COND1(true,x,y) -> COND2(gr(x,y),x,y) COND2(false,x,y) -> COND3(eq(x,y),x,y) COND2(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) COND3(false,x,y) -> COND1(gr(add(x,y),0),x,p(y)) COND3(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Narrowed Pairs: ->->Original Pair: COND1(true,x,y) -> COND2(gr(x,y),x,y) ->-> Narrowed pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) ->->Original Pair: COND2(false,x,y) -> COND3(eq(x,y),x,y) ->-> Narrowed pairs: COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),0) -> COND3(false,s(x),0) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) ->->Original Pair: COND2(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) ->-> Narrowed pairs: COND2(true,0,x) -> COND1(gr(x,0),p(0),x) COND2(true,0,x7) -> COND1(gr(add(0,x7),0),0,x7) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND2(true,s(x),x7) -> COND1(gr(add(s(x),x7),0),x,x7) ->->Original Pair: COND3(false,x,y) -> COND1(gr(add(x,y),0),x,p(y)) ->-> Narrowed pairs: COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(false,x8,0) -> COND1(gr(add(x8,0),0),x8,0) COND3(false,x8,s(x)) -> COND1(gr(add(x8,s(x)),0),x8,x) ->->Original Pair: COND3(true,x,y) -> COND1(gr(add(x,y),0),p(x),y) ->-> Narrowed pairs: COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) Problem 1.4: SCC Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),0) -> COND3(false,s(x),0) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,0,x) -> COND1(gr(x,0),p(0),x) COND2(true,0,x7) -> COND1(gr(add(0,x7),0),0,x7) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND2(true,s(x),x7) -> COND1(gr(add(s(x),x7),0),x,x7) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(false,x8,0) -> COND1(gr(add(x8,0),0),x8,0) COND3(false,x8,s(x)) -> COND1(gr(add(x8,s(x)),0),x8,x) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND2(true,s(x),x7) -> COND1(gr(add(s(x),x7),0),x,x7) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(false,x8,s(x)) -> COND1(gr(add(x8,s(x)),0),x8,x) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 Problem 1.4: Reduction Pairs Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND2(true,s(x),x7) -> COND1(gr(add(s(x),x7),0),x,x7) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(false,x8,s(x)) -> COND1(gr(add(x8,s(x)),0),x8,x) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 + X2 + 2 [eq](X1,X2) = 1 [gr](X1,X2) = 2.X1 + 2.X2 + 2 [p](X) = X [0] = 2 [false] = 1 [s](X) = X + 1 [true] = 1 [COND1](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND2](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND3](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 Problem 1.4: SCC Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(false,x8,s(x)) -> COND1(gr(add(x8,s(x)),0),x8,x) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(false,x8,s(x)) -> COND1(gr(add(x8,s(x)),0),x8,x) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 Problem 1.4: Reduction Pairs Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(false,x8,s(x)) -> COND1(gr(add(x8,s(x)),0),x8,x) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 + X2 [eq](X1,X2) = 1 [gr](X1,X2) = 1 [p](X) = X [0] = 2 [false] = 1 [s](X) = X + 1 [true] = 1 [COND1](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 1 [COND2](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2 [COND3](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2 Problem 1.4: SCC Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 Problem 1.4: Reduction Pairs Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(true,s(x),x11) -> COND1(gr(add(s(x),x11),0),x,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 [eq](X1,X2) = 0 [gr](X1,X2) = 2.X1 + 2.X2 + 2 [p](X) = X [0] = 2 [false] = 0 [s](X) = X + 2 [true] = 0 [COND1](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND2](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND3](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 Problem 1.4: SCC Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 Problem 1.4: Reduction Pairs Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),0) -> COND2(true,s(x),0) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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) = 2.X1.X2 + 2.X1 + X2 [eq](X1,X2) = 2 [gr](X1,X2) = 1 [p](X) = 1/2.X [0] = 0 [false] = 1 [s](X) = 2.X + 1/2 [true] = 0 [COND1](X1,X2,X3) = 1/2.X1.X2.X3 + X2.X3 + 2.X2 + 2.X3 [COND2](X1,X2,X3) = X1.X2 + X2.X3 + X2 + 2.X3 [COND3](X1,X2,X3) = X2.X3 + 2.X2 + 2.X3 Problem 1.4: SCC Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 Problem 1.4: Reduction Pairs Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND1(true,s(x),s(y)) -> COND2(gr(x,y),s(x),s(y)) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 -> Usable rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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) = 2.X1.X2 + X1 + X2 [eq](X1,X2) = 1/2 [gr](X1,X2) = 1/2 [p](X) = 1/2.X [0] = 0 [false] = 1/2 [s](X) = 2.X + 1/2 [true] = 1/2 [COND1](X1,X2,X3) = 2.X1.X2.X3 + 1/2.X1.X2 + 2.X1.X3 + 1/2.X2.X3 + 1/2.X1 + 1/2.X2 + X3 + 2 [COND2](X1,X2,X3) = 1/2.X1.X2.X3 + X1.X2 + 2.X1.X3 + X2.X3 + 1/2.X1 + X3 + 2 [COND3](X1,X2,X3) = 1/2.X1.X2.X3 + 1/2.X1.X2 + 2.X1.X3 + 1/2.X2.X3 + 1/2.X1 + 1/2.X2 + X3 + 2 Problem 1.4: SCC Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND2(false,s(x),s(y)) -> COND3(eq(x,y),s(x),s(y)) COND2(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(false,s(x),y) -> COND1(gr(s(add(x,y)),0),s(x),p(y)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) COND3(true,s(x),y) -> COND1(gr(s(add(x,y)),0),p(s(x)),y) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) ->->-> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 Problem 1.4: Reduction Pairs Processor: -> Pairs: COND1(true,0,x) -> COND2(false,0,x) COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 -> 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) = 2.X1.X2 + 1/2.X1 + 1/2.X2 [p](X) = 1/2.X [0] = 0 [false] = 0 [s](X) = 2.X + 2 [true] = 1/2 [COND1](X1,X2,X3) = 2.X2.X3 + 2.X1 + 1/2.X2 + 2.X3 [COND2](X1,X2,X3) = 1/2.X1.X3 + 1/2.X2.X3 + 2.X2 + 2.X3 + 1/2 [COND3](X1,X2,X3) = 2.X1.X2 + 2.X1.X3 + 1/2.X2.X3 + 1/2.X1 + 2.X2 + 2.X3 Problem 1.4: SCC Processor: -> Pairs: COND2(false,0,0) -> COND3(true,0,0) COND2(false,0,s(x)) -> COND3(false,0,s(x)) COND3(false,0,x) -> COND1(gr(x,0),0,p(x)) COND3(true,0,x) -> COND1(gr(x,0),p(0),x) COND3(true,0,x11) -> COND1(gr(add(0,x11),0),0,x11) -> Rules: add(0,x) -> x add(s(x),y) -> s(add(x,y)) cond1(true,x,y) -> cond2(gr(x,y),x,y) cond2(false,x,y) -> cond3(eq(x,y),x,y) cond2(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) cond3(false,x,y) -> cond1(gr(add(x,y),0),x,p(y)) cond3(true,x,y) -> cond1(gr(add(x,y),0),p(x),y) eq(0,0) -> true eq(0,s(x)) -> false eq(s(x),0) -> false eq(s(x),s(y)) -> eq(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 ->Strongly Connected Components: There is no strongly connected component The problem is finite.