/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Problem 1: (VAR x y z) (RULES *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ) Problem 1: Dependency Pairs Processor: -> Pairs: *#(*(x,y),z) -> *#(x,*(y,z)) *#(*(x,y),z) -> *#(y,z) *#(+(x,y),z) -> *#(x,z) *#(+(x,y),z) -> *#(y,z) *#(+(x,y),z) -> +#(*(x,z),*(y,z)) *#(0(x),y) -> *#(x,y) *#(0(x),y) -> 0#(*(x,y)) *#(1(x),y) -> *#(x,y) *#(1(x),y) -> +#(0(*(x,y)),y) *#(1(x),y) -> 0#(*(x,y)) *#(j(x),y) -> *#(x,y) *#(j(x),y) -> -#(0(*(x,y)),y) *#(j(x),y) -> 0#(*(x,y)) *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) *#(x,+(y,z)) -> +#(*(x,y),*(x,z)) +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),0(y)) -> +#(x,y) +#(0(x),0(y)) -> 0#(+(x,y)) +#(0(x),1(y)) -> +#(x,y) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(1(x),j(y)) -> 0#(+(x,y)) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),1(y)) -> 0#(+(x,y)) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -#(x,y) -> +#(x,opp(y)) -#(x,y) -> OPP(y) OPP(0(x)) -> 0#(opp(x)) OPP(0(x)) -> OPP(x) OPP(1(x)) -> OPP(x) OPP(j(x)) -> OPP(x) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1: SCC Processor: -> Pairs: *#(*(x,y),z) -> *#(x,*(y,z)) *#(*(x,y),z) -> *#(y,z) *#(+(x,y),z) -> *#(x,z) *#(+(x,y),z) -> *#(y,z) *#(+(x,y),z) -> +#(*(x,z),*(y,z)) *#(0(x),y) -> *#(x,y) *#(0(x),y) -> 0#(*(x,y)) *#(1(x),y) -> *#(x,y) *#(1(x),y) -> +#(0(*(x,y)),y) *#(1(x),y) -> 0#(*(x,y)) *#(j(x),y) -> *#(x,y) *#(j(x),y) -> -#(0(*(x,y)),y) *#(j(x),y) -> 0#(*(x,y)) *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) *#(x,+(y,z)) -> +#(*(x,y),*(x,z)) +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),0(y)) -> +#(x,y) +#(0(x),0(y)) -> 0#(+(x,y)) +#(0(x),1(y)) -> +#(x,y) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(1(x),j(y)) -> 0#(+(x,y)) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),1(y)) -> 0#(+(x,y)) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -#(x,y) -> +#(x,opp(y)) -#(x,y) -> OPP(y) OPP(0(x)) -> 0#(opp(x)) OPP(0(x)) -> OPP(x) OPP(1(x)) -> OPP(x) OPP(j(x)) -> OPP(x) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: OPP(0(x)) -> OPP(x) OPP(1(x)) -> OPP(x) OPP(j(x)) -> OPP(x) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->->Cycle: ->->-> Pairs: *#(*(x,y),z) -> *#(x,*(y,z)) *#(*(x,y),z) -> *#(y,z) *#(+(x,y),z) -> *#(x,z) *#(+(x,y),z) -> *#(y,z) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) *#(j(x),y) -> *#(x,y) *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) The problem is decomposed in 3 subproblems. Problem 1.1: Subterm Processor: -> Pairs: OPP(0(x)) -> OPP(x) OPP(1(x)) -> OPP(x) OPP(j(x)) -> OPP(x) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Projection: pi(OPP) = 1 Problem 1.1: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 2 [#] = 0 [1](X) = X + 1 [j](X) = X + 1 [+#](X1,X2) = 2.X1 + 2.X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),1(y)) -> +#(x,y) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),1(y)) -> +#(x,y) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),1(y)) -> +#(x,y) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 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,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(0(x),j(y)) -> +#(x,y) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 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,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),0(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 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,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),1(y)) -> +#(+(x,y),1(#)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 0(#) -> # ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [+](X1,X2) = X1 + X2 [0](X) = X + 2 [#] = 0 [1](X) = X + 1 [j](X) = X + 1 [+#](X1,X2) = X1 + X2 Problem 1.2: SCC Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),1(y)) -> +#(x,y) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 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,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(1(x),j(y)) -> +#(x,y) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 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,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),0(y)) -> +#(x,y) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 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,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),1(y)) -> +#(x,y) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 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,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Reduction Pair Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),j(y)) -> +#(+(x,y),j(#)) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) -> Usable rules: +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x 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,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),j(y)) -> +#(x,y) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.2: Subterm Processor: -> Pairs: +#(+(x,y),z) -> +#(x,+(y,z)) +#(+(x,y),z) -> +#(y,z) +#(j(x),j(y)) -> +#(x,y) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Projection: pi(+#) = 1 Problem 1.2: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> Pairs: *#(*(x,y),z) -> *#(x,*(y,z)) *#(*(x,y),z) -> *#(y,z) *#(+(x,y),z) -> *#(x,z) *#(+(x,y),z) -> *#(y,z) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) *#(j(x),y) -> *#(x,y) *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Projection: pi(*#) = 1 Problem 1.3: SCC Processor: -> Pairs: *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) ->->-> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) Problem 1.3: Subterm Processor: -> Pairs: *#(x,+(y,z)) -> *#(x,y) *#(x,+(y,z)) -> *#(x,z) -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Projection: pi(*#) = 2 Problem 1.3: SCC Processor: -> Pairs: Empty -> Rules: *(*(x,y),z) -> *(x,*(y,z)) *(+(x,y),z) -> +(*(x,z),*(y,z)) *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) *(j(x),y) -> -(0(*(x,y)),y) *(x,+(y,z)) -> +(*(x,y),*(x,z)) +(+(x,y),z) -> +(x,+(y,z)) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(0(x),j(y)) -> j(+(x,y)) +(#,x) -> x +(1(x),0(y)) -> 1(+(x,y)) +(1(x),1(y)) -> j(+(+(x,y),1(#))) +(1(x),j(y)) -> 0(+(x,y)) +(j(x),0(y)) -> j(+(x,y)) +(j(x),1(y)) -> 0(+(x,y)) +(j(x),j(y)) -> 1(+(+(x,y),j(#))) +(x,#) -> x -(x,y) -> +(x,opp(y)) 0(#) -> # opp(0(x)) -> 0(opp(x)) opp(#) -> # opp(1(x)) -> j(opp(x)) opp(j(x)) -> 1(opp(x)) ->Strongly Connected Components: There is no strongly connected component The problem is finite.