/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 cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ) Problem 1: Innermost Equivalent Processor: -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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: COND1(true,x,y) -> COND2(gr(x,0),x,y) COND1(true,x,y) -> GR(x,0) COND2(false,x,y) -> COND3(gr(y,0),x,y) COND2(false,x,y) -> GR(y,0) COND2(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),p(x),y) COND2(true,x,y) -> GR(x,0) COND2(true,x,y) -> GR(y,0) COND2(true,x,y) -> OR(gr(x,0),gr(y,0)) COND2(true,x,y) -> P(x) COND3(false,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,y) COND3(false,x,y) -> GR(x,0) COND3(false,x,y) -> GR(y,0) COND3(false,x,y) -> OR(gr(x,0),gr(y,0)) COND3(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,p(y)) COND3(true,x,y) -> GR(x,0) COND3(true,x,y) -> GR(y,0) COND3(true,x,y) -> OR(gr(x,0),gr(y,0)) COND3(true,x,y) -> P(y) GR(s(x),s(y)) -> GR(x,y) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1: SCC Processor: -> Pairs: COND1(true,x,y) -> COND2(gr(x,0),x,y) COND1(true,x,y) -> GR(x,0) COND2(false,x,y) -> COND3(gr(y,0),x,y) COND2(false,x,y) -> GR(y,0) COND2(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),p(x),y) COND2(true,x,y) -> GR(x,0) COND2(true,x,y) -> GR(y,0) COND2(true,x,y) -> OR(gr(x,0),gr(y,0)) COND2(true,x,y) -> P(x) COND3(false,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,y) COND3(false,x,y) -> GR(x,0) COND3(false,x,y) -> GR(y,0) COND3(false,x,y) -> OR(gr(x,0),gr(y,0)) COND3(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,p(y)) COND3(true,x,y) -> GR(x,0) COND3(true,x,y) -> GR(y,0) COND3(true,x,y) -> OR(gr(x,0),gr(y,0)) COND3(true,x,y) -> P(y) GR(s(x),s(y)) -> GR(x,y) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: GR(s(x),s(y)) -> GR(x,y) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->->Cycle: ->->-> Pairs: COND1(true,x,y) -> COND2(gr(x,0),x,y) COND2(false,x,y) -> COND3(gr(y,0),x,y) COND2(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),p(x),y) COND3(false,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,y) COND3(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,p(y)) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x The problem is decomposed in 2 subproblems. Problem 1.1: Subterm Processor: -> Pairs: GR(s(x),s(y)) -> GR(x,y) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Projection: pi(GR) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Narrowing Processor: -> Pairs: COND1(true,x,y) -> COND2(gr(x,0),x,y) COND2(false,x,y) -> COND3(gr(y,0),x,y) COND2(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),p(x),y) COND3(false,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,y) COND3(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,p(y)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Narrowed Pairs: ->->Original Pair: COND1(true,x,y) -> COND2(gr(x,0),x,y) ->-> Narrowed pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) ->->Original Pair: COND2(false,x,y) -> COND3(gr(y,0),x,y) ->-> Narrowed pairs: COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) ->->Original Pair: COND2(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),p(x),y) ->-> Narrowed pairs: COND2(true,0,x7) -> COND1(or(gr(0,0),gr(x7,0)),0,x7) COND2(true,0,x7) -> COND1(or(false,gr(x7,0)),p(0),x7) COND2(true,s(x),x7) -> COND1(or(gr(s(x),0),gr(x7,0)),x,x7) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) ->->Original Pair: COND3(false,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,y) ->-> Narrowed pairs: COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(false,x8,s(x)) -> COND1(or(gr(x8,0),true),x8,s(x)) ->->Original Pair: COND3(true,x,y) -> COND1(or(gr(x,0),gr(y,0)),x,p(y)) ->-> Narrowed pairs: COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,0) -> COND1(or(gr(x10,0),gr(0,0)),x10,0) COND3(true,x10,0) -> COND1(or(gr(x10,0),false),x10,p(0)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),gr(s(x),0)),x10,x) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,0,x7) -> COND1(or(gr(0,0),gr(x7,0)),0,x7) COND2(true,0,x7) -> COND1(or(false,gr(x7,0)),p(0),x7) COND2(true,s(x),x7) -> COND1(or(gr(s(x),0),gr(x7,0)),x,x7) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(false,x8,s(x)) -> COND1(or(gr(x8,0),true),x8,s(x)) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,0) -> COND1(or(gr(x10,0),gr(0,0)),x10,0) COND3(true,x10,0) -> COND1(or(gr(x10,0),false),x10,p(0)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),gr(s(x),0)),x10,x) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,s(x),x7) -> COND1(or(gr(s(x),0),gr(x7,0)),x,x7) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),gr(s(x),0)),x10,x) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,s(x),x7) -> COND1(or(gr(s(x),0),gr(x7,0)),x,x7) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),gr(s(x),0)),x10,x) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = 2.X2 + 2 [or](X1,X2) = 2 [p](X) = X [0] = 1 [false] = 2 [s](X) = 2.X + 2 [true] = 2 [COND1](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND2](X1,X2,X3) = X1 + 2.X2 + 2.X3 [COND3](X1,X2,X3) = 2.X2 + 2.X3 + 2 Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),gr(s(x),0)),x10,x) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),gr(s(x),0)),x10,x) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),gr(s(x),0)),x10,x) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = 2 [or](X1,X2) = X1 + 2 [p](X) = X [0] = 2 [false] = 2 [s](X) = 2.X + 1 [true] = 2 [COND1](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND2](X1,X2,X3) = X1 + 2.X2 + 2.X3 [COND3](X1,X2,X3) = 2.X2 + 2.X3 + 2 Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,s(x),x7) -> COND1(or(true,gr(x7,0)),p(s(x)),x7) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = 2.X2 + 2 [or](X1,X2) = 1 [p](X) = 1/2.X [0] = 0 [false] = 1 [s](X) = 2.X + 2 [true] = 1 [COND1](X1,X2,X3) = 1/2.X1 + X2 + 2.X3 + 1/2 [COND2](X1,X2,X3) = X1 + X2 + 2.X3 [COND3](X1,X2,X3) = 1/2.X1 + X2 + 2.X3 + 1/2 Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) COND3(true,x10,s(x)) -> COND1(or(gr(x10,0),true),x10,p(s(x))) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = 2.X1 + 2 [or](X1,X2) = X2 + 2 [p](X) = 1/2.X [0] = 0 [false] = 2 [s](X) = 2.X + 1/2 [true] = 2 [COND1](X1,X2,X3) = 1/2.X2 + 1/2.X3 + 2 [COND2](X1,X2,X3) = 1/2.X1 + 1/2.X2 + 1/2.X3 + 1 [COND3](X1,X2,X3) = X1 + 1/2.X2 + 1/2.X3 Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,s(x),x9) -> COND1(or(true,gr(x9,0)),s(x),x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = 2.X1 + 2 [or](X1,X2) = 2.X1.X2 [p](X) = 2.X.X + 2 [0] = 0 [false] = 2 [s](X) = 2.X + 2 [true] = 0 [COND1](X1,X2,X3) = 2 [COND2](X1,X2,X3) = 2.X1.X2.X3 + 2.X1.X2 + 2 [COND3](X1,X2,X3) = 2.X1.X2.X3 + X1.X2 + 2.X1.X3 + 2.X2 + 2 Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) COND3(true,s(x),x11) -> COND1(or(true,gr(x11,0)),s(x),p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = 2 [or](X1,X2) = 2 [p](X) = X [0] = 0 [false] = 2 [s](X) = 2.X.X + 2.X + 2 [true] = 0 [COND1](X1,X2,X3) = 2.X2.X3 + X3 + 2 [COND2](X1,X2,X3) = 2.X1.X2 + 2.X2.X3 + X3 + 2 [COND3](X1,X2,X3) = 2.X1.X2.X3 + 2.X1.X3 + 2.X2.X3 + 2.X2 + X3 + 2 Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND1(true,s(x),x3) -> COND2(true,s(x),x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Interpretation type: Simple mixed ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = 1/2.X1.X2 + 2.X2 + 1/2 [or](X1,X2) = 2.X2 [p](X) = 1/2.X [0] = 0 [false] = 1/2 [s](X) = 2.X + 1/2 [true] = 0 [COND1](X1,X2,X3) = X1.X3 + X2.X3 + 2.X2 + X3 + 2 [COND2](X1,X2,X3) = 2.X1.X2 + X2.X3 + X2 + X3 + 2 [COND3](X1,X2,X3) = 2.X1.X3 + 2.X2 + X3 + 2 Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND2(true,x6,0) -> COND1(or(gr(x6,0),false),p(x6),0) COND2(true,x6,s(x)) -> COND1(or(gr(x6,0),true),p(x6),s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(false,x8,0) -> COND1(or(gr(x8,0),false),x8,0) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 2 ->Bound: 1 ->Interpretation: [gr](X1,X2) = [0 1;0 0].X1 + [0;1] [or](X1,X2) = [1 0;0 0].X1 + [0 1;0 0].X2 + [0;1] [p](X) = [0 1;0 1].X + [1;0] [0] = 0 [false] = 0 [s](X) = [0 0;1 1].X + [0;1] [true] = [1;1] [COND1](X1,X2,X3) = [1 0;0 0].X1 + [1 0;1 1].X2 + [0 1;0 0].X3 + [0;1] [COND2](X1,X2,X3) = [1 0;1 0].X1 + [1 1;1 1].X2 + [0 1;0 0].X3 + [1;1] [COND3](X1,X2,X3) = [1 1;1 1].X2 + [0 1;0 0].X3 + [1;1] Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND2(false,x4,0) -> COND3(false,x4,0) COND2(false,x4,s(x)) -> COND3(true,x4,s(x)) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Interpretation type: Simple mixed ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = 1/2.X1.X2 + 1/2.X1 + 2.X2 + 1/2 [or](X1,X2) = X1 [p](X) = 1/2.X [0] = 0 [false] = 1/2 [s](X) = X.X + 2.X + 2 [true] = 0 [COND1](X1,X2,X3) = X2.X3 + X3 + 1 [COND2](X1,X2,X3) = 1/2.X1.X2 + 2.X1.X3 + X1 + 2.X2 + 1/2 [COND3](X1,X2,X3) = 2.X1.X2.X3 + 1/2.X1.X2 + 2.X1.X3 + 1/2.X3 + 1 Problem 1.2: SCC Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND2(false,x4,0) -> COND3(false,x4,0) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) COND3(true,0,x11) -> COND1(or(false,gr(x11,0)),0,p(x11)) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND2(false,x4,0) -> COND3(false,x4,0) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) ->->-> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(true,0,x3) -> COND2(false,0,x3) COND2(false,x4,0) -> COND3(false,x4,0) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true 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) or(false,false) -> false or(true,x) -> true or(x,true) -> true ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [gr](X1,X2) = X1 [or](X1,X2) = 2.X1 + X2 [0] = 0 [false] = 0 [s](X) = 2.X + 2 [true] = 2 [COND1](X1,X2,X3) = 2.X1 + 2 [COND2](X1,X2,X3) = 2.X1 + 2.X2 + 2 [COND3](X1,X2,X3) = 2.X1 + 2.X3 + 2 Problem 1.2: SCC Processor: -> Pairs: COND2(false,x4,0) -> COND3(false,x4,0) COND3(false,0,x9) -> COND1(or(false,gr(x9,0)),0,x9) -> Rules: cond1(true,x,y) -> cond2(gr(x,0),x,y) cond2(false,x,y) -> cond3(gr(y,0),x,y) cond2(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),p(x),y) cond3(false,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,y) cond3(true,x,y) -> cond1(or(gr(x,0),gr(y,0)),x,p(y)) gr(0,x) -> false gr(s(x),0) -> true gr(s(x),s(y)) -> gr(x,y) or(false,false) -> false or(true,x) -> true or(x,true) -> true p(0) -> 0 p(s(x)) -> x ->Strongly Connected Components: There is no strongly connected component The problem is finite.