YES Problem 1: (VAR v_NonEmpty:S x:S y:S) (RULES and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ) Problem 1: Innermost Equivalent Processor: -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> The term rewriting system is non-overlaping or locally confluent overlay system. Therefore, innermost termination implies termination. Problem 1: Dependency Pairs Processor: -> Pairs: COND1(ttrue,x:S,y:S) -> COND2(gr(x:S,y:S),x:S,y:S) COND1(ttrue,x:S,y:S) -> GR(x:S,y:S) COND2(ffalse,x:S,y:S) -> COND4(gr(y:S,0),x:S,y:S) COND2(ffalse,x:S,y:S) -> GR(y:S,0) COND2(ttrue,x:S,y:S) -> COND3(gr(x:S,0),x:S,y:S) COND2(ttrue,x:S,y:S) -> GR(x:S,0) COND3(ffalse,x:S,y:S) -> AND(gr(x:S,0),gr(y:S,0)) COND3(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) COND3(ffalse,x:S,y:S) -> GR(x:S,0) COND3(ffalse,x:S,y:S) -> GR(y:S,0) COND3(ttrue,x:S,y:S) -> COND3(gr(x:S,0),p(x:S),y:S) COND3(ttrue,x:S,y:S) -> GR(x:S,0) COND3(ttrue,x:S,y:S) -> P(x:S) COND4(ffalse,x:S,y:S) -> AND(gr(x:S,0),gr(y:S,0)) COND4(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) COND4(ffalse,x:S,y:S) -> GR(x:S,0) COND4(ffalse,x:S,y:S) -> GR(y:S,0) COND4(ttrue,x:S,y:S) -> COND4(gr(y:S,0),x:S,p(y:S)) COND4(ttrue,x:S,y:S) -> GR(y:S,0) COND4(ttrue,x:S,y:S) -> P(y:S) GR(s(x:S),s(y:S)) -> GR(x:S,y:S) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S Problem 1: SCC Processor: -> Pairs: COND1(ttrue,x:S,y:S) -> COND2(gr(x:S,y:S),x:S,y:S) COND1(ttrue,x:S,y:S) -> GR(x:S,y:S) COND2(ffalse,x:S,y:S) -> COND4(gr(y:S,0),x:S,y:S) COND2(ffalse,x:S,y:S) -> GR(y:S,0) COND2(ttrue,x:S,y:S) -> COND3(gr(x:S,0),x:S,y:S) COND2(ttrue,x:S,y:S) -> GR(x:S,0) COND3(ffalse,x:S,y:S) -> AND(gr(x:S,0),gr(y:S,0)) COND3(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) COND3(ffalse,x:S,y:S) -> GR(x:S,0) COND3(ffalse,x:S,y:S) -> GR(y:S,0) COND3(ttrue,x:S,y:S) -> COND3(gr(x:S,0),p(x:S),y:S) COND3(ttrue,x:S,y:S) -> GR(x:S,0) COND3(ttrue,x:S,y:S) -> P(x:S) COND4(ffalse,x:S,y:S) -> AND(gr(x:S,0),gr(y:S,0)) COND4(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) COND4(ffalse,x:S,y:S) -> GR(x:S,0) COND4(ffalse,x:S,y:S) -> GR(y:S,0) COND4(ttrue,x:S,y:S) -> COND4(gr(y:S,0),x:S,p(y:S)) COND4(ttrue,x:S,y:S) -> GR(y:S,0) COND4(ttrue,x:S,y:S) -> P(y:S) GR(s(x:S),s(y:S)) -> GR(x:S,y:S) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: GR(s(x:S),s(y:S)) -> GR(x:S,y:S) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->->Cycle: ->->-> Pairs: COND1(ttrue,x:S,y:S) -> COND2(gr(x:S,y:S),x:S,y:S) COND2(ffalse,x:S,y:S) -> COND4(gr(y:S,0),x:S,y:S) COND2(ttrue,x:S,y:S) -> COND3(gr(x:S,0),x:S,y:S) COND3(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) COND3(ttrue,x:S,y:S) -> COND3(gr(x:S,0),p(x:S),y:S) COND4(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) COND4(ttrue,x:S,y:S) -> COND4(gr(y:S,0),x:S,p(y:S)) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S The problem is decomposed in 2 subproblems. Problem 1.1: Subterm Processor: -> Pairs: GR(s(x:S),s(y:S)) -> GR(x:S,y:S) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Projection: pi(GR) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Narrowing Processor: -> Pairs: COND1(ttrue,x:S,y:S) -> COND2(gr(x:S,y:S),x:S,y:S) COND2(ffalse,x:S,y:S) -> COND4(gr(y:S,0),x:S,y:S) COND2(ttrue,x:S,y:S) -> COND3(gr(x:S,0),x:S,y:S) COND3(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) COND3(ttrue,x:S,y:S) -> COND3(gr(x:S,0),p(x:S),y:S) COND4(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) COND4(ttrue,x:S,y:S) -> COND4(gr(y:S,0),x:S,p(y:S)) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Narrowed Pairs: ->->Original Pair: COND1(ttrue,x:S,y:S) -> COND2(gr(x:S,y:S),x:S,y:S) ->-> Narrowed pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) ->->Original Pair: COND2(ffalse,x:S,y:S) -> COND4(gr(y:S,0),x:S,y:S) ->-> Narrowed pairs: COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) ->->Original Pair: COND2(ttrue,x:S,y:S) -> COND3(gr(x:S,0),x:S,y:S) ->-> Narrowed pairs: COND2(ttrue,0,x8:S) -> COND3(ffalse,0,x8:S) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) ->->Original Pair: COND3(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) ->-> Narrowed pairs: COND3(ffalse,0,x10:S) -> COND1(and(ffalse,gr(x10:S,0)),0,x10:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,0) -> COND1(and(gr(x9:S,0),ffalse),x9:S,0) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) ->->Original Pair: COND3(ttrue,x:S,y:S) -> COND3(gr(x:S,0),p(x:S),y:S) ->-> Narrowed pairs: COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) ->->Original Pair: COND4(ffalse,x:S,y:S) -> COND1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) ->-> Narrowed pairs: COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) ->->Original Pair: COND4(ttrue,x:S,y:S) -> COND4(gr(y:S,0),x:S,p(y:S)) ->-> Narrowed pairs: COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) Problem 1.2: SCC Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,0,x8:S) -> COND3(ffalse,0,x8:S) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,0,x10:S) -> COND1(and(ffalse,gr(x10:S,0)),0,x10:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,0) -> COND1(and(gr(x9:S,0),ffalse),x9:S,0) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,0,x10:S) -> COND1(and(ffalse,gr(x10:S,0)),0,x10:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,0) -> COND1(and(gr(x9:S,0),ffalse),x9:S,0) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,0,x10:S) -> COND1(and(ffalse,gr(x10:S,0)),0,x10:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,0) -> COND1(and(gr(x9:S,0),ffalse),x9:S,0) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = X1 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = 2 [p](X) = X [0] = 0 [fSNonEmpty] = 0 [false] = 0 [s](X) = 2.X + 2 [true] = 2 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = X1 + 2.X2 + 2.X3 [COND2](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND3](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND4](X1,X2,X3) = 2.X2 + 2.X3 + 2 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2: SCC Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,0) -> COND1(and(gr(x9:S,0),ffalse),x9:S,0) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,0) -> COND1(and(gr(x9:S,0),ffalse),x9:S,0) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,0) -> COND1(and(gr(x9:S,0),ffalse),x9:S,0) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = X2 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = 2 [p](X) = X [0] = 2 [fSNonEmpty] = 0 [false] = 0 [s](X) = 2.X + 2 [true] = 2 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = X1 + 2.X2 [COND2](X1,X2,X3) = 2.X2 + 2 [COND3](X1,X2,X3) = 2.X2 + 2 [COND4](X1,X2,X3) = 2.X2 + 2 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2: SCC Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(gr(s(x:S),0),x:S,x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = 2.X1 + X2 + 2 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = 2.X1 + 2 [p](X) = X [0] = 2 [fSNonEmpty] = 0 [false] = 2 [s](X) = 2.X + 2 [true] = 2 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = 2.X2 + X3 + 2 [COND2](X1,X2,X3) = 2.X2 + X3 + 2 [COND3](X1,X2,X3) = 2.X2 + X3 + 2 [COND4](X1,X2,X3) = 2.X2 + X3 + 2 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2: SCC Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,0,x14:S) -> COND1(and(ffalse,gr(x14:S,0)),0,x14:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = X1 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = 2 [p](X) = X [0] = 0 [fSNonEmpty] = 0 [false] = 0 [s](X) = 2.X [true] = 2 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = X1 + 2.X2 + 2.X3 [COND2](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND3](X1,X2,X3) = 2.X2 + 2.X3 + 2 [COND4](X1,X2,X3) = 2.X2 + 2.X3 + 2 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2: SCC Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,0) -> COND1(and(gr(x13:S,0),ffalse),x13:S,0) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = X2 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = 2.X2 [p](X) = 2.X + 1 [0] = 1 [fSNonEmpty] = 0 [false] = 0 [s](X) = 2.X [true] = 2 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = X1 [COND2](X1,X2,X3) = 2 [COND3](X1,X2,X3) = 2 [COND4](X1,X2,X3) = 2 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2: SCC Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(gr(s(x:S),0),x15:S,x:S) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = 2 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = 2 [p](X) = X [0] = 2 [fSNonEmpty] = 0 [false] = 2 [s](X) = 2.X + 2 [true] = 2 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 [COND2](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 [COND3](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 [COND4](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2: SCC Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S Problem 1.2: Reduction Pairs Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND3(ttrue,s(x:S),x12:S) -> COND3(ttrue,p(s(x:S)),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = 1 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = 1/2.X1 [p](X) = 1/2.X [0] = 0 [fSNonEmpty] = 0 [false] = 0 [s](X) = 2.X + 2 [true] = 1 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = 2.X1 + 2.X2 + X3 [COND2](X1,X2,X3) = 2.X2 + X3 + 2 [COND3](X1,X2,X3) = 2.X2 + X3 + 2 [COND4](X1,X2,X3) = 2.X2 + X3 + 2 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2: SCC Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),0) -> COND2(ttrue,s(x:S),0) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND2(ttrue,s(x:S),x8:S) -> COND3(ttrue,s(x:S),x8:S) COND3(ffalse,s(x:S),x10:S) -> COND1(and(ttrue,gr(x10:S,0)),s(x:S),x10:S) COND3(ffalse,x9:S,s(x:S)) -> COND1(and(gr(x9:S,0),ttrue),x9:S,s(x:S)) COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) COND3(ttrue,0,x12:S) -> COND3(ffalse,p(0),x12:S) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->->Cycle: ->->-> Pairs: COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S The problem is decomposed in 2 subproblems. Problem 1.2.1: Reduction Pairs Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) COND4(ttrue,x15:S,s(x:S)) -> COND4(ttrue,x15:S,p(s(x:S))) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Interpretation type: Linear ->Coefficients: All rationals ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = 2 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = 2 [p](X) = 1/2.X [0] = 0 [fSNonEmpty] = 0 [false] = 2 [s](X) = 2.X + 1/2 [true] = 2 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = 2.X1 + 1/2.X3 + 1/2 [COND2](X1,X2,X3) = 2.X1 + 1/2.X3 + 1/2 [COND3](X1,X2,X3) = 0 [COND4](X1,X2,X3) = 2.X1 + 1/2.X3 + 1/2 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2.1: SCC Processor: -> Pairs: COND1(ttrue,0,x:S) -> COND2(ffalse,0,x:S) COND1(ttrue,s(x:S),s(y:S)) -> COND2(gr(x:S,y:S),s(x:S),s(y:S)) COND2(ffalse,x5:S,0) -> COND4(ffalse,x5:S,0) COND2(ffalse,x5:S,s(x:S)) -> COND4(ttrue,x5:S,s(x:S)) COND4(ffalse,s(x:S),x14:S) -> COND1(and(ttrue,gr(x14:S,0)),s(x:S),x14:S) COND4(ffalse,x13:S,s(x:S)) -> COND1(and(gr(x13:S,0),ttrue),x13:S,s(x:S)) COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) COND4(ttrue,x15:S,0) -> COND4(ffalse,x15:S,p(0)) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) ->->-> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S Problem 1.2.1: Reduction Pairs Processor: -> Pairs: COND4(ttrue,x15:S,0) -> COND4(gr(0,0),x15:S,0) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = 0 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = X1 + 1 [p](X) = 0 [0] = 0 [fSNonEmpty] = 0 [false] = 1 [s](X) = X + 1 [true] = 2 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = 0 [COND2](X1,X2,X3) = 0 [COND3](X1,X2,X3) = 0 [COND4](X1,X2,X3) = X1 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2.1: SCC Processor: -> Pairs: Empty -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2.2: Reduction Pairs Processor: -> Pairs: COND3(ttrue,0,x12:S) -> COND3(gr(0,0),0,x12:S) -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S -> Usable rules: gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [and](X1,X2) = 0 [cond1](X1,X2,X3) = 0 [cond2](X1,X2,X3) = 0 [cond3](X1,X2,X3) = 0 [cond4](X1,X2,X3) = 0 [gr](X1,X2) = X1 + 1 [p](X) = 0 [0] = 0 [fSNonEmpty] = 0 [false] = 1 [s](X) = X + 1 [true] = 2 [AND](X1,X2) = 0 [COND1](X1,X2,X3) = 0 [COND2](X1,X2,X3) = 0 [COND3](X1,X2,X3) = X1 [COND4](X1,X2,X3) = 0 [GR](X1,X2) = 0 [P](X) = 0 Problem 1.2.2: SCC Processor: -> Pairs: Empty -> Rules: and(ffalse,x:S) -> ffalse and(ttrue,ttrue) -> ttrue and(x:S,ffalse) -> ffalse cond1(ttrue,x:S,y:S) -> cond2(gr(x:S,y:S),x:S,y:S) cond2(ffalse,x:S,y:S) -> cond4(gr(y:S,0),x:S,y:S) cond2(ttrue,x:S,y:S) -> cond3(gr(x:S,0),x:S,y:S) cond3(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond3(ttrue,x:S,y:S) -> cond3(gr(x:S,0),p(x:S),y:S) cond4(ffalse,x:S,y:S) -> cond1(and(gr(x:S,0),gr(y:S,0)),x:S,y:S) cond4(ttrue,x:S,y:S) -> cond4(gr(y:S,0),x:S,p(y:S)) gr(0,x:S) -> ffalse gr(s(x:S),0) -> ttrue gr(s(x:S),s(y:S)) -> gr(x:S,y:S) p(0) -> 0 p(s(x:S)) -> x:S ->Strongly Connected Components: There is no strongly connected component The problem is finite.