YES Problem 1: (VAR v_NonEmpty:S x:S y:S z:S) (RULES *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ) Problem 1: Dependency Pairs Processor: -> Pairs: *#(*(x:S,y:S),z:S) -> *#(x:S,*(y:S,z:S)) *#(*(x:S,y:S),z:S) -> *#(y:S,z:S) *#(0(x:S),y:S) -> *#(x:S,y:S) *#(0(x:S),y:S) -> 0#(*(x:S,y:S)) *#(1(x:S),y:S) -> *#(x:S,y:S) *#(1(x:S),y:S) -> +#(0(*(x:S,y:S)),y:S) *#(1(x:S),y:S) -> 0#(*(x:S,y:S)) *#(j(x:S),y:S) -> *#(x:S,y:S) *#(j(x:S),y:S) -> -#(0(*(x:S,y:S)),y:S) *#(j(x:S),y:S) -> 0#(*(x:S,y:S)) +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),0(y:S)) -> 0#(+(x:S,y:S)) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> 0#(+(x:S,y:S)) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> 0#(+(x:S,y:S)) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -#(x:S,y:S) -> +#(x:S,opp(y:S)) -#(x:S,y:S) -> OPP(y:S) OPP(0(x:S)) -> 0#(opp(x:S)) OPP(0(x:S)) -> OPP(x:S) OPP(1(x:S)) -> OPP(x:S) OPP(j(x:S)) -> OPP(x:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1: SCC Processor: -> Pairs: *#(*(x:S,y:S),z:S) -> *#(x:S,*(y:S,z:S)) *#(*(x:S,y:S),z:S) -> *#(y:S,z:S) *#(0(x:S),y:S) -> *#(x:S,y:S) *#(0(x:S),y:S) -> 0#(*(x:S,y:S)) *#(1(x:S),y:S) -> *#(x:S,y:S) *#(1(x:S),y:S) -> +#(0(*(x:S,y:S)),y:S) *#(1(x:S),y:S) -> 0#(*(x:S,y:S)) *#(j(x:S),y:S) -> *#(x:S,y:S) *#(j(x:S),y:S) -> -#(0(*(x:S,y:S)),y:S) *#(j(x:S),y:S) -> 0#(*(x:S,y:S)) +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),0(y:S)) -> 0#(+(x:S,y:S)) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> 0#(+(x:S,y:S)) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> 0#(+(x:S,y:S)) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -#(x:S,y:S) -> +#(x:S,opp(y:S)) -#(x:S,y:S) -> OPP(y:S) OPP(0(x:S)) -> 0#(opp(x:S)) OPP(0(x:S)) -> OPP(x:S) OPP(1(x:S)) -> OPP(x:S) OPP(j(x:S)) -> OPP(x:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: OPP(0(x:S)) -> OPP(x:S) OPP(1(x:S)) -> OPP(x:S) OPP(j(x:S)) -> OPP(x:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->->Cycle: ->->-> Pairs: *#(*(x:S,y:S),z:S) -> *#(x:S,*(y:S,z:S)) *#(*(x:S,y:S),z:S) -> *#(y:S,z:S) *#(0(x:S),y:S) -> *#(x:S,y:S) *#(1(x:S),y:S) -> *#(x:S,y:S) *#(j(x:S),y:S) -> *#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) The problem is decomposed in 3 subproblems. Problem 1.1: Subterm Processor: -> Pairs: OPP(0(x:S)) -> OPP(x:S) OPP(1(x:S)) -> OPP(x:S) OPP(j(x:S)) -> OPP(x:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Projection: pi(OPP) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),0(y:S)) -> +#(x:S,y:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 1 [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),1(y:S)) -> +#(x:S,y:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 1 [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = X1 + X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(0(x:S),j(y:S)) -> +#(x:S,y:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 2 [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = X1 + X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),0(y:S)) -> +#(x:S,y:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 1 [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),1(y:S)) -> +#(+(x:S,y:S),1(#)) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),1(y:S)) -> +#(x:S,y:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 2 [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = X1 + X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(1(x:S),j(y:S)) -> +#(x:S,y:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 2 [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = X1 + X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),0(y:S)) -> +#(x:S,y:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 2 [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),1(y:S)) -> +#(x:S,y:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 1 [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),j(y:S)) -> +#(+(x:S,y:S),j(#)) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) -> Usable rules: +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 2 [#] = 0 [1](X) = X + 2 [j](X) = X + 2 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) ->->-> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) Problem 1.2: Subterm Processor: -> Pairs: +#(+(x:S,y:S),z:S) -> +#(x:S,+(y:S,z:S)) +#(+(x:S,y:S),z:S) -> +#(y:S,z:S) +#(j(x:S),j(y:S)) -> +#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Projection: pi(+#) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: *#(*(x:S,y:S),z:S) -> *#(x:S,*(y:S,z:S)) *#(*(x:S,y:S),z:S) -> *#(y:S,z:S) *#(0(x:S),y:S) -> *#(x:S,y:S) *#(1(x:S),y:S) -> *#(x:S,y:S) *#(j(x:S),y:S) -> *#(x:S,y:S) -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Projection: pi(*#) = 1 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: *(*(x:S,y:S),z:S) -> *(x:S,*(y:S,z:S)) *(0(x:S),y:S) -> 0(*(x:S,y:S)) *(#,x:S) -> # *(1(x:S),y:S) -> +(0(*(x:S,y:S)),y:S) *(j(x:S),y:S) -> -(0(*(x:S,y:S)),y:S) +(+(x:S,y:S),z:S) -> +(x:S,+(y:S,z:S)) +(0(x:S),0(y:S)) -> 0(+(x:S,y:S)) +(0(x:S),1(y:S)) -> 1(+(x:S,y:S)) +(0(x:S),j(y:S)) -> j(+(x:S,y:S)) +(#,x:S) -> x:S +(1(x:S),0(y:S)) -> 1(+(x:S,y:S)) +(1(x:S),1(y:S)) -> j(+(+(x:S,y:S),1(#))) +(1(x:S),j(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),0(y:S)) -> j(+(x:S,y:S)) +(j(x:S),1(y:S)) -> 0(+(x:S,y:S)) +(j(x:S),j(y:S)) -> 1(+(+(x:S,y:S),j(#))) +(x:S,#) -> x:S -(x:S,y:S) -> +(x:S,opp(y:S)) 0(#) -> # opp(0(x:S)) -> 0(opp(x:S)) opp(#) -> # opp(1(x:S)) -> j(opp(x:S)) opp(j(x:S)) -> 1(opp(x:S)) ->Strongly Connected Components: There is no strongly connected component The problem is finite.