YES Problem 1: (VAR b x y) (THEORY (AC * + U)) (RULES *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x ) Problem 1: Dependency Pairs Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) U#(U(x3,x4),x5) = U#(x3,U(x4,x5)) U#(x3,x4) = U#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(0(x),y),x3) -> *#(x,y) *#(*(0(x),y),x3) -> 0#(*(x,y)) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(+(0(*(x,y)),y),x3) *#(*(1(x),y),x3) -> *#(x,y) *#(*(1(x),y),x3) -> +#(0(*(x,y)),y) *#(*(1(x),y),x3) -> 0#(*(x,y)) *#(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)) +#(+(0(x),0(y)),x3) -> +#(0(+(x,y)),x3) +#(+(0(x),0(y)),x3) -> +#(x,y) +#(+(0(x),0(y)),x3) -> 0#(+(x,y)) +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(+(1(x),1(y)),x3) -> 0#(+(1(#),+(x,y))) +#(0(x),0(y)) -> +#(x,y) +#(0(x),0(y)) -> 0#(+(x,y)) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> 0#(+(1(#),+(x,y))) U#(U(empty,b),x3) -> U#(b,x3) PROD(U(x,y)) -> *#(prod(x),prod(y)) PROD(U(x,y)) -> PROD(x) PROD(U(x,y)) -> PROD(y) SUM(U(x,y)) -> +#(sum(x),sum(y)) SUM(U(x,y)) -> SUM(x) SUM(U(x,y)) -> SUM(y) SUM(empty) -> 0#(#) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) U#(U(x3,x4),x5) -> U#(x3,x4) U#(x3,U(x4,x5)) -> U#(x4,x5) Problem 1: SCC Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) U#(U(x3,x4),x5) = U#(x3,U(x4,x5)) U#(x3,x4) = U#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(0(x),y),x3) -> *#(x,y) *#(*(0(x),y),x3) -> 0#(*(x,y)) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(+(0(*(x,y)),y),x3) *#(*(1(x),y),x3) -> *#(x,y) *#(*(1(x),y),x3) -> +#(0(*(x,y)),y) *#(*(1(x),y),x3) -> 0#(*(x,y)) *#(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)) +#(+(0(x),0(y)),x3) -> +#(0(+(x,y)),x3) +#(+(0(x),0(y)),x3) -> +#(x,y) +#(+(0(x),0(y)),x3) -> 0#(+(x,y)) +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(+(1(x),1(y)),x3) -> 0#(+(1(#),+(x,y))) +#(0(x),0(y)) -> +#(x,y) +#(0(x),0(y)) -> 0#(+(x,y)) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> 0#(+(1(#),+(x,y))) U#(U(empty,b),x3) -> U#(b,x3) PROD(U(x,y)) -> *#(prod(x),prod(y)) PROD(U(x,y)) -> PROD(x) PROD(U(x,y)) -> PROD(y) SUM(U(x,y)) -> +#(sum(x),sum(y)) SUM(U(x,y)) -> SUM(x) SUM(U(x,y)) -> SUM(y) SUM(empty) -> 0#(#) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) U#(U(x3,x4),x5) -> U#(x3,x4) U#(x3,U(x4,x5)) -> U#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: U#(U(empty,b),x3) -> U#(b,x3) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) U#(U(x3,x4),x5) -> U#(x3,U(x4,x5)) U#(x3,x4) -> U#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: U#(U(x3,x4),x5) -> U#(x3,x4) U#(x3,U(x4,x5)) -> U#(x4,x5) ->->Cycle: ->->-> Pairs: +#(+(0(x),0(y)),x3) -> +#(0(+(x,y)),x3) +#(+(0(x),0(y)),x3) -> +#(x,y) +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->->Cycle: ->->-> Pairs: SUM(U(x,y)) -> SUM(x) SUM(U(x,y)) -> SUM(y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: Empty ->->Cycle: ->->-> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(0(x),y),x3) -> *#(x,y) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(+(0(*(x,y)),y),x3) *#(*(1(x),y),x3) -> *#(x,y) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) *#(*(x3,x4),x5) -> *#(x3,*(x4,x5)) *#(x3,x4) -> *#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->->Cycle: ->->-> Pairs: PROD(U(x,y)) -> PROD(x) PROD(U(x,y)) -> PROD(y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: Empty The problem is decomposed in 5 subproblems. Problem 1.1: Reduction Pairs Processor: -> FAxioms: U#(U(x3,x4),x5) = U#(x3,U(x4,x5)) U#(x3,x4) = U#(x4,x3) -> Pairs: U#(U(empty,b),x3) -> U#(b,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: U(empty,b) -> b -> SRules: U#(U(x3,x4),x5) -> U#(x3,x4) U#(x3,U(x4,x5)) -> U#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = 0 [0](X) = 0 [U](X1,X2) = X1 + X2 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = 0 [empty] = 2 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 0 [0#](X) = 0 [U#](X1,X2) = 2.X1 + 2.X2 [PROD](X) = 0 [SUM](X) = 0 Problem 1.1: SCC Processor: -> FAxioms: U#(U(x3,x4),x5) = U#(x3,U(x4,x5)) U#(x3,x4) = U#(x4,x3) -> Pairs: Empty -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: U#(U(x3,x4),x5) -> U#(x3,x4) U#(x3,U(x4,x5)) -> U#(x4,x5) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(0(x),0(y)),x3) -> +#(0(+(x,y)),x3) +#(+(0(x),0(y)),x3) -> +#(x,y) +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 + 1 [0](X) = X + 1 [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 2.X1 + 2.X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(0(x),0(y)),x3) -> +#(x,y) +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(0(x),0(y)),x3) -> +#(x,y) +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(0(x),0(y)),x3) -> +#(x,y) +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 [0](X) = X + 1 [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 1 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = X1 + X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(0(x),1(y)),x3) -> +#(1(+(x,y)),x3) +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 [0](X) = X + 1 [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 1 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = X1 + X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(0(x),1(y)),x3) -> +#(x,y) +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 + 2 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 2.X1 + 2.X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(#,x),x3) -> +#(x,x3) +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 + 1 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 1 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 2.X1 + 2.X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(1(x),1(y)),x3) -> +#(0(+(1(#),+(x,y))),x3) +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 1 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = X1 + X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(1(x),1(y)),x3) -> +#(1(#),+(x,y)) +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 + 1 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 1 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 2.X1 + 2.X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(+(1(x),1(y)),x3) -> +#(x,y) +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 [0](X) = 2.X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = 2.X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 2.X1 + 2.X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(+(x3,x4),x5) -> +#(x3,x4) +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 + 1 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = X + 1 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 2.X1 + 2.X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(0(x),0(y)) -> +#(x,y) +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 + 1 [0](X) = X + 1 [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 2.X1 + 2.X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(0(x),1(y)) -> +#(x,y) +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 + 2 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = X1 + X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(1(x),1(y)) -> +#(1(#),+(x,y)) +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 [0](X) = X + 1 [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = X + 2 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 2.X1 + 2.X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: +#(1(x),1(y)) -> +#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) +#(+(x3,x4),x5) -> +#(x3,+(x4,x5)) +#(x3,x4) -> +#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) Problem 1.2: Reduction Pairs Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: +#(1(x),1(y)) -> +#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = 0 [+](X1,X2) = X1 + X2 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 1 [1](X) = X + 1 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 0 [+#](X1,X2) = 2.X1 + 2.X2 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.2: SCC Processor: -> FAxioms: +#(+(x3,x4),x5) = +#(x3,+(x4,x5)) +#(x3,x4) = +#(x4,x3) -> Pairs: Empty -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: +#(x3,+(x4,x5)) -> +#(x4,x5) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.3: Subterm Processor: -> FAxioms: Empty -> Pairs: SUM(U(x,y)) -> SUM(x) SUM(U(x,y)) -> SUM(y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: Empty ->Projection: pi(SUM) = [1] Problem 1.3: SCC Processor: -> FAxioms: Empty -> Pairs: Empty -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.4: Reduction Pairs Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(0(x),y),x3) -> *#(x,y) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(+(0(*(x,y)),y),x3) *#(*(1(x),y),x3) -> *#(x,y) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [*](X1,X2) = X1.X2 + X1 + X2 [+](X1,X2) = X1 + X2 [0](X) = X + 1 [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = X + 1 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = X1.X2 + X1 + X2 [+#](X1,X2) = 0 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.4: SCC Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(+(0(*(x,y)),y),x3) *#(*(1(x),y),x3) -> *#(x,y) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(+(0(*(x,y)),y),x3) *#(*(1(x),y),x3) -> *#(x,y) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) *#(*(x3,x4),x5) -> *#(x3,*(x4,x5)) *#(x3,x4) -> *#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) Problem 1.4: Reduction Pairs Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(+(0(*(x,y)),y),x3) *#(*(1(x),y),x3) -> *#(x,y) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [*](X1,X2) = X1.X2 + X1 + X2 [+](X1,X2) = X1 + X2 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 1 [1](X) = X + 1 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = X1.X2 + X1 + X2 [+#](X1,X2) = 0 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.4: SCC Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(x,y) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(x,y) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) *#(*(x3,x4),x5) -> *#(x3,*(x4,x5)) *#(x3,x4) -> *#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) Problem 1.4: Reduction Pairs Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(*(1(x),y),x3) -> *#(x,y) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [*](X1,X2) = X1.X2 + X1 + X2 [+](X1,X2) = X1 + X2 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 1 [1](X) = X + 1 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = X1.X2 + X1 + X2 [+#](X1,X2) = 0 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.4: SCC Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) *#(*(x3,x4),x5) -> *#(x3,*(x4,x5)) *#(x3,x4) -> *#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) Problem 1.4: Reduction Pairs Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(0(x),y) -> *#(x,y) *#(1(x),y) -> *#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [*](X1,X2) = X1.X2 + X1 + X2 [+](X1,X2) = X1 + X2 [0](X) = X + 1 [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = X + 1 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = X1.X2 + X1 + X2 [+#](X1,X2) = 0 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.4: SCC Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(1(x),y) -> *#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(1(x),y) -> *#(x,y) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) *#(*(x3,x4),x5) -> *#(x3,*(x4,x5)) *#(x3,x4) -> *#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) Problem 1.4: Reduction Pairs Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) *#(1(x),y) -> *#(x,y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Interpretation type: Simple mixed ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 1 ->Interpretation: [*](X1,X2) = X1.X2 + X1 + X2 [+](X1,X2) = X1 + X2 [0](X) = X [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 1 [1](X) = X + 1 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = X1.X2 + X1 + X2 [+#](X1,X2) = 0 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.4: SCC Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) *#(*(x3,x4),x5) -> *#(x3,*(x4,x5)) *#(x3,x4) -> *#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) Problem 1.4: Reduction Pairs Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(0(x),y),x3) -> *#(0(*(x,y)),x3) *#(*(#,x),x3) -> *#(#,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = X1 + X2 + 2 [+](X1,X2) = X1 + X2 + 1 [0](X) = 2 [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 2 [1](X) = 1 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 2.X1 + 2.X2 [+#](X1,X2) = 0 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.4: SCC Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(#,x),x3) -> *#(#,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Strongly Connected Components: ->->Cycle: ->->-> Pairs: *#(*(#,x),x3) -> *#(#,x3) -> FAxioms: *(*(x3,x4),x5) -> *(x3,*(x4,x5)) *(x3,x4) -> *(x4,x3) +(+(x3,x4),x5) -> +(x3,+(x4,x5)) +(x3,x4) -> +(x4,x3) U(U(x3,x4),x5) -> U(x3,U(x4,x5)) U(x3,x4) -> U(x4,x3) *#(*(x3,x4),x5) -> *#(x3,*(x4,x5)) *#(x3,x4) -> *#(x4,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) ->->-> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) Problem 1.4: Reduction Pairs Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: *#(*(#,x),x3) -> *#(#,x3) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Usable Equations: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> Usable Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Interpretation type: Linear ->Coefficients: Natural Numbers ->Dimension: 1 ->Bound: 2 ->Interpretation: [*](X1,X2) = X1 + X2 + 2 [+](X1,X2) = X1 + X2 [0](X) = 0 [U](X1,X2) = 0 [prod](X) = 0 [sum](X) = 0 [#] = 0 [1](X) = 0 [empty] = 0 [singl](X) = 0 [*#](X1,X2) = 2.X1 + 2.X2 [+#](X1,X2) = 0 [0#](X) = 0 [U#](X1,X2) = 0 [PROD](X) = 0 [SUM](X) = 0 Problem 1.4: SCC Processor: -> FAxioms: *#(*(x3,x4),x5) = *#(x3,*(x4,x5)) *#(x3,x4) = *#(x4,x3) -> Pairs: Empty -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: *#(*(x3,x4),x5) -> *#(x3,x4) *#(x3,*(x4,x5)) -> *#(x4,x5) ->Strongly Connected Components: There is no strongly connected component The problem is finite. Problem 1.5: Subterm Processor: -> FAxioms: Empty -> Pairs: PROD(U(x,y)) -> PROD(x) PROD(U(x,y)) -> PROD(y) -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: Empty ->Projection: pi(PROD) = [1] Problem 1.5: SCC Processor: -> FAxioms: Empty -> Pairs: Empty -> EAxioms: *(*(x3,x4),x5) = *(x3,*(x4,x5)) *(x3,x4) = *(x4,x3) +(+(x3,x4),x5) = +(x3,+(x4,x5)) +(x3,x4) = +(x4,x3) U(U(x3,x4),x5) = U(x3,U(x4,x5)) U(x3,x4) = U(x4,x3) -> Rules: *(0(x),y) -> 0(*(x,y)) *(#,x) -> # *(1(x),y) -> +(0(*(x,y)),y) +(0(x),0(y)) -> 0(+(x,y)) +(0(x),1(y)) -> 1(+(x,y)) +(#,x) -> x +(1(x),1(y)) -> 0(+(1(#),+(x,y))) 0(#) -> # U(empty,b) -> b prod(U(x,y)) -> *(prod(x),prod(y)) prod(empty) -> 1(#) prod(singl(x)) -> x sum(U(x,y)) -> +(sum(x),sum(y)) sum(empty) -> 0(#) sum(singl(x)) -> x -> SRules: Empty ->Strongly Connected Components: There is no strongly connected component The problem is finite.