2.51/2.55 YES 2.51/2.55 2.51/2.55 Problem 1: 2.51/2.55 2.51/2.55 (VAR A B X Y) 2.51/2.55 (THEORY 2.51/2.55 (AC mult plus union)) 2.51/2.55 (RULES 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 ) 2.51/2.55 2.51/2.55 Problem 1: 2.51/2.55 2.51/2.55 Dependency Pairs Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.55 MULT(x4,x5) = MULT(x5,x4) 2.51/2.55 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.55 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.55 UNION(union(x4,x5),x6) = UNION(x4,union(x5,x6)) 2.51/2.55 UNION(x4,x5) = UNION(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 U11#(tt,X,Y) -> U12#(tt,X,Y) 2.51/2.55 U12#(tt,X,Y) -> 0#(mult(X,Y)) 2.51/2.55 U12#(tt,X,Y) -> MULT(X,Y) 2.51/2.55 U21#(tt,X,Y) -> U22#(tt,X,Y) 2.51/2.55 U22#(tt,X,Y) -> 0#(mult(X,Y)) 2.51/2.55 U22#(tt,X,Y) -> MULT(X,Y) 2.51/2.55 U22#(tt,X,Y) -> PLUS(0(mult(X,Y)),Y) 2.51/2.55 U31#(tt,X,Y) -> U32#(tt,X,Y) 2.51/2.55 U32#(tt,X,Y) -> 0#(plus(X,Y)) 2.51/2.55 U32#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U41#(tt,X,Y) -> U42#(tt,X,Y) 2.51/2.55 U42#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.55 U52#(tt,X,Y) -> 0#(plus(plus(X,Y),1(z))) 2.51/2.55 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.55 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U61#(tt,A,B) -> U62#(tt,A,B) 2.51/2.55 U62#(tt,A,B) -> MULT(prod(A),prod(B)) 2.51/2.55 U62#(tt,A,B) -> PROD(A) 2.51/2.55 U62#(tt,A,B) -> PROD(B) 2.51/2.55 U71#(tt,A,B) -> U72#(tt,A,B) 2.51/2.55 U72#(tt,A,B) -> PLUS(sum(A),sum(B)) 2.51/2.55 U72#(tt,A,B) -> SUM(A) 2.51/2.55 U72#(tt,A,B) -> SUM(B) 2.51/2.55 MULT(0(X),Y) -> U11#(tt,X,Y) 2.51/2.55 MULT(mult(0(X),Y),x4) -> U11#(tt,X,Y) 2.51/2.55 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.55 MULT(mult(1(X),Y),x4) -> U21#(tt,X,Y) 2.51/2.55 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.55 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.55 MULT(1(X),Y) -> U21#(tt,X,Y) 2.51/2.55 PLUS(0(X),0(Y)) -> U31#(tt,X,Y) 2.51/2.55 PLUS(0(X),1(Y)) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> U31#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.55 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.55 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.55 PROD(union(A,B)) -> U61#(tt,A,B) 2.51/2.55 SUM(union(A,B)) -> U71#(tt,A,B) 2.51/2.55 SUM(empty) -> 0#(z) 2.51/2.55 UNION(union(empty,X),x4) -> UNION(X,x4) 2.51/2.55 UNION(union(X,empty),x4) -> UNION(X,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.55 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.55 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,x5) 2.51/2.55 UNION(x4,union(x5,x6)) -> UNION(x5,x6) 2.51/2.55 2.51/2.55 Problem 1: 2.51/2.55 2.51/2.55 SCC Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.55 MULT(x4,x5) = MULT(x5,x4) 2.51/2.55 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.55 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.55 UNION(union(x4,x5),x6) = UNION(x4,union(x5,x6)) 2.51/2.55 UNION(x4,x5) = UNION(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 U11#(tt,X,Y) -> U12#(tt,X,Y) 2.51/2.55 U12#(tt,X,Y) -> 0#(mult(X,Y)) 2.51/2.55 U12#(tt,X,Y) -> MULT(X,Y) 2.51/2.55 U21#(tt,X,Y) -> U22#(tt,X,Y) 2.51/2.55 U22#(tt,X,Y) -> 0#(mult(X,Y)) 2.51/2.55 U22#(tt,X,Y) -> MULT(X,Y) 2.51/2.55 U22#(tt,X,Y) -> PLUS(0(mult(X,Y)),Y) 2.51/2.55 U31#(tt,X,Y) -> U32#(tt,X,Y) 2.51/2.55 U32#(tt,X,Y) -> 0#(plus(X,Y)) 2.51/2.55 U32#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U41#(tt,X,Y) -> U42#(tt,X,Y) 2.51/2.55 U42#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.55 U52#(tt,X,Y) -> 0#(plus(plus(X,Y),1(z))) 2.51/2.55 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.55 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U61#(tt,A,B) -> U62#(tt,A,B) 2.51/2.55 U62#(tt,A,B) -> MULT(prod(A),prod(B)) 2.51/2.55 U62#(tt,A,B) -> PROD(A) 2.51/2.55 U62#(tt,A,B) -> PROD(B) 2.51/2.55 U71#(tt,A,B) -> U72#(tt,A,B) 2.51/2.55 U72#(tt,A,B) -> PLUS(sum(A),sum(B)) 2.51/2.55 U72#(tt,A,B) -> SUM(A) 2.51/2.55 U72#(tt,A,B) -> SUM(B) 2.51/2.55 MULT(0(X),Y) -> U11#(tt,X,Y) 2.51/2.55 MULT(mult(0(X),Y),x4) -> U11#(tt,X,Y) 2.51/2.55 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.55 MULT(mult(1(X),Y),x4) -> U21#(tt,X,Y) 2.51/2.55 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.55 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.55 MULT(1(X),Y) -> U21#(tt,X,Y) 2.51/2.55 PLUS(0(X),0(Y)) -> U31#(tt,X,Y) 2.51/2.55 PLUS(0(X),1(Y)) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> U31#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.55 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.55 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.55 PROD(union(A,B)) -> U61#(tt,A,B) 2.51/2.55 SUM(union(A,B)) -> U71#(tt,A,B) 2.51/2.55 SUM(empty) -> 0#(z) 2.51/2.55 UNION(union(empty,X),x4) -> UNION(X,x4) 2.51/2.55 UNION(union(X,empty),x4) -> UNION(X,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.55 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.55 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,x5) 2.51/2.55 UNION(x4,union(x5,x6)) -> UNION(x5,x6) 2.51/2.55 ->Strongly Connected Components: 2.51/2.55 ->->Cycle: 2.51/2.55 ->->-> Pairs: 2.51/2.55 UNION(union(empty,X),x4) -> UNION(X,x4) 2.51/2.55 UNION(union(X,empty),x4) -> UNION(X,x4) 2.51/2.55 -> FAxioms: 2.51/2.55 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) -> mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) -> plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) -> union(x5,x4) 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,union(x5,x6)) 2.51/2.55 UNION(x4,x5) -> UNION(x5,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 ->->-> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,x5) 2.51/2.55 UNION(x4,union(x5,x6)) -> UNION(x5,x6) 2.51/2.55 ->->Cycle: 2.51/2.55 ->->-> Pairs: 2.51/2.55 U31#(tt,X,Y) -> U32#(tt,X,Y) 2.51/2.55 U32#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U41#(tt,X,Y) -> U42#(tt,X,Y) 2.51/2.55 U42#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.55 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.55 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 PLUS(0(X),0(Y)) -> U31#(tt,X,Y) 2.51/2.55 PLUS(0(X),1(Y)) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> U31#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.55 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.55 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.55 -> FAxioms: 2.51/2.55 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) -> mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) -> plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) -> union(x5,x4) 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,plus(x5,x6)) 2.51/2.55 PLUS(x4,x5) -> PLUS(x5,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 ->->-> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.55 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.55 ->->Cycle: 2.51/2.55 ->->-> Pairs: 2.51/2.55 U71#(tt,A,B) -> U72#(tt,A,B) 2.51/2.55 U72#(tt,A,B) -> SUM(A) 2.51/2.55 U72#(tt,A,B) -> SUM(B) 2.51/2.55 SUM(union(A,B)) -> U71#(tt,A,B) 2.51/2.55 -> FAxioms: 2.51/2.55 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) -> mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) -> plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) -> union(x5,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 ->->-> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 Empty 2.51/2.55 ->->Cycle: 2.51/2.55 ->->-> Pairs: 2.51/2.55 U11#(tt,X,Y) -> U12#(tt,X,Y) 2.51/2.55 U12#(tt,X,Y) -> MULT(X,Y) 2.51/2.55 U21#(tt,X,Y) -> U22#(tt,X,Y) 2.51/2.55 U22#(tt,X,Y) -> MULT(X,Y) 2.51/2.55 MULT(0(X),Y) -> U11#(tt,X,Y) 2.51/2.55 MULT(mult(0(X),Y),x4) -> U11#(tt,X,Y) 2.51/2.55 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.55 MULT(mult(1(X),Y),x4) -> U21#(tt,X,Y) 2.51/2.55 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.55 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.55 MULT(1(X),Y) -> U21#(tt,X,Y) 2.51/2.55 -> FAxioms: 2.51/2.55 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) -> mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) -> plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) -> union(x5,x4) 2.51/2.55 MULT(mult(x4,x5),x6) -> MULT(x4,mult(x5,x6)) 2.51/2.55 MULT(x4,x5) -> MULT(x5,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 ->->-> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.55 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.55 ->->Cycle: 2.51/2.55 ->->-> Pairs: 2.51/2.55 U61#(tt,A,B) -> U62#(tt,A,B) 2.51/2.55 U62#(tt,A,B) -> PROD(A) 2.51/2.55 U62#(tt,A,B) -> PROD(B) 2.51/2.55 PROD(union(A,B)) -> U61#(tt,A,B) 2.51/2.55 -> FAxioms: 2.51/2.55 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) -> mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) -> plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) -> union(x5,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 ->->-> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 Empty 2.51/2.55 2.51/2.55 2.51/2.55 The problem is decomposed in 5 subproblems. 2.51/2.55 2.51/2.55 Problem 1.1: 2.51/2.55 2.51/2.55 Reduction Pairs Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 UNION(union(x4,x5),x6) = UNION(x4,union(x5,x6)) 2.51/2.55 UNION(x4,x5) = UNION(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 UNION(union(empty,X),x4) -> UNION(X,x4) 2.51/2.55 UNION(union(X,empty),x4) -> UNION(X,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Usable Equations: 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> Usable Rules: 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,x5) 2.51/2.55 UNION(x4,union(x5,x6)) -> UNION(x5,x6) 2.51/2.55 ->Interpretation type: 2.51/2.55 Linear 2.51/2.55 ->Coefficients: 2.51/2.55 Natural Numbers 2.51/2.55 ->Dimension: 2.51/2.55 1 2.51/2.55 ->Bound: 2.51/2.55 2 2.51/2.55 ->Interpretation: 2.51/2.55 2.51/2.55 [0](X) = 0 2.51/2.55 [U11](X1,X2,X3) = 0 2.51/2.55 [U12](X1,X2,X3) = 0 2.51/2.55 [U21](X1,X2,X3) = 0 2.51/2.55 [U22](X1,X2,X3) = 0 2.51/2.55 [U31](X1,X2,X3) = 0 2.51/2.55 [U32](X1,X2,X3) = 0 2.51/2.55 [U41](X1,X2,X3) = 0 2.51/2.55 [U42](X1,X2,X3) = 0 2.51/2.55 [U51](X1,X2,X3) = 0 2.51/2.55 [U52](X1,X2,X3) = 0 2.51/2.55 [U61](X1,X2,X3) = 0 2.51/2.55 [U62](X1,X2,X3) = 0 2.51/2.55 [U71](X1,X2,X3) = 0 2.51/2.55 [U72](X1,X2,X3) = 0 2.51/2.55 [mult](X1,X2) = 0 2.51/2.55 [plus](X1,X2) = 0 2.51/2.55 [prod](X) = 0 2.51/2.55 [sum](X) = 0 2.51/2.55 [union](X1,X2) = X1 + X2 2.51/2.55 [1](X) = 0 2.51/2.55 [empty] = 2 2.51/2.55 [singl](X) = 0 2.51/2.55 [tt] = 0 2.51/2.55 [z] = 0 2.51/2.55 [0#](X) = 0 2.51/2.55 [U11#](X1,X2,X3) = 0 2.51/2.55 [U12#](X1,X2,X3) = 0 2.51/2.55 [U21#](X1,X2,X3) = 0 2.51/2.55 [U22#](X1,X2,X3) = 0 2.51/2.55 [U31#](X1,X2,X3) = 0 2.51/2.55 [U32#](X1,X2,X3) = 0 2.51/2.55 [U41#](X1,X2,X3) = 0 2.51/2.55 [U42#](X1,X2,X3) = 0 2.51/2.55 [U51#](X1,X2,X3) = 0 2.51/2.55 [U52#](X1,X2,X3) = 0 2.51/2.55 [U61#](X1,X2,X3) = 0 2.51/2.55 [U62#](X1,X2,X3) = 0 2.51/2.55 [U71#](X1,X2,X3) = 0 2.51/2.55 [U72#](X1,X2,X3) = 0 2.51/2.55 [MULT](X1,X2) = 0 2.51/2.55 [PLUS](X1,X2) = 0 2.51/2.55 [PROD](X) = 0 2.51/2.55 [SUM](X) = 0 2.51/2.55 [UNION](X1,X2) = 2.X1 + 2.X2 2.51/2.55 2.51/2.55 Problem 1.1: 2.51/2.55 2.51/2.55 SCC Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 UNION(union(x4,x5),x6) = UNION(x4,union(x5,x6)) 2.51/2.55 UNION(x4,x5) = UNION(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 UNION(union(X,empty),x4) -> UNION(X,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,x5) 2.51/2.55 UNION(x4,union(x5,x6)) -> UNION(x5,x6) 2.51/2.55 ->Strongly Connected Components: 2.51/2.55 ->->Cycle: 2.51/2.55 ->->-> Pairs: 2.51/2.55 UNION(union(X,empty),x4) -> UNION(X,x4) 2.51/2.55 -> FAxioms: 2.51/2.55 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) -> mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) -> plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) -> union(x5,x4) 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,union(x5,x6)) 2.51/2.55 UNION(x4,x5) -> UNION(x5,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 ->->-> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,x5) 2.51/2.55 UNION(x4,union(x5,x6)) -> UNION(x5,x6) 2.51/2.55 2.51/2.55 Problem 1.1: 2.51/2.55 2.51/2.55 Reduction Pairs Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 UNION(union(x4,x5),x6) = UNION(x4,union(x5,x6)) 2.51/2.55 UNION(x4,x5) = UNION(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 UNION(union(X,empty),x4) -> UNION(X,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Usable Equations: 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> Usable Rules: 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,x5) 2.51/2.55 UNION(x4,union(x5,x6)) -> UNION(x5,x6) 2.51/2.55 ->Interpretation type: 2.51/2.55 Linear 2.51/2.55 ->Coefficients: 2.51/2.55 Natural Numbers 2.51/2.55 ->Dimension: 2.51/2.55 1 2.51/2.55 ->Bound: 2.51/2.55 2 2.51/2.55 ->Interpretation: 2.51/2.55 2.51/2.55 [0](X) = 0 2.51/2.55 [U11](X1,X2,X3) = 0 2.51/2.55 [U12](X1,X2,X3) = 0 2.51/2.55 [U21](X1,X2,X3) = 0 2.51/2.55 [U22](X1,X2,X3) = 0 2.51/2.55 [U31](X1,X2,X3) = 0 2.51/2.55 [U32](X1,X2,X3) = 0 2.51/2.55 [U41](X1,X2,X3) = 0 2.51/2.55 [U42](X1,X2,X3) = 0 2.51/2.55 [U51](X1,X2,X3) = 0 2.51/2.55 [U52](X1,X2,X3) = 0 2.51/2.55 [U61](X1,X2,X3) = 0 2.51/2.55 [U62](X1,X2,X3) = 0 2.51/2.55 [U71](X1,X2,X3) = 0 2.51/2.55 [U72](X1,X2,X3) = 0 2.51/2.55 [mult](X1,X2) = 0 2.51/2.55 [plus](X1,X2) = 0 2.51/2.55 [prod](X) = 0 2.51/2.55 [sum](X) = 0 2.51/2.55 [union](X1,X2) = X1 + X2 + 2 2.51/2.55 [1](X) = 0 2.51/2.55 [empty] = 2 2.51/2.55 [singl](X) = 0 2.51/2.55 [tt] = 0 2.51/2.55 [z] = 0 2.51/2.55 [0#](X) = 0 2.51/2.55 [U11#](X1,X2,X3) = 0 2.51/2.55 [U12#](X1,X2,X3) = 0 2.51/2.55 [U21#](X1,X2,X3) = 0 2.51/2.55 [U22#](X1,X2,X3) = 0 2.51/2.55 [U31#](X1,X2,X3) = 0 2.51/2.55 [U32#](X1,X2,X3) = 0 2.51/2.55 [U41#](X1,X2,X3) = 0 2.51/2.55 [U42#](X1,X2,X3) = 0 2.51/2.55 [U51#](X1,X2,X3) = 0 2.51/2.55 [U52#](X1,X2,X3) = 0 2.51/2.55 [U61#](X1,X2,X3) = 0 2.51/2.55 [U62#](X1,X2,X3) = 0 2.51/2.55 [U71#](X1,X2,X3) = 0 2.51/2.55 [U72#](X1,X2,X3) = 0 2.51/2.55 [MULT](X1,X2) = 0 2.51/2.55 [PLUS](X1,X2) = 0 2.51/2.55 [PROD](X) = 0 2.51/2.55 [SUM](X) = 0 2.51/2.55 [UNION](X1,X2) = 2.X1 + 2.X2 2.51/2.55 2.51/2.55 Problem 1.1: 2.51/2.55 2.51/2.55 SCC Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 UNION(union(x4,x5),x6) = UNION(x4,union(x5,x6)) 2.51/2.55 UNION(x4,x5) = UNION(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 Empty 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 UNION(union(x4,x5),x6) -> UNION(x4,x5) 2.51/2.55 UNION(x4,union(x5,x6)) -> UNION(x5,x6) 2.51/2.55 ->Strongly Connected Components: 2.51/2.55 There is no strongly connected component 2.51/2.55 2.51/2.55 The problem is finite. 2.51/2.55 2.51/2.55 Problem 1.2: 2.51/2.55 2.51/2.55 Reduction Pairs Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.55 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 U31#(tt,X,Y) -> U32#(tt,X,Y) 2.51/2.55 U32#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U41#(tt,X,Y) -> U42#(tt,X,Y) 2.51/2.55 U42#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.55 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.55 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 PLUS(0(X),0(Y)) -> U31#(tt,X,Y) 2.51/2.55 PLUS(0(X),1(Y)) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> U31#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.55 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.55 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Usable Equations: 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> Usable Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 -> SRules: 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.55 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.55 ->Interpretation type: 2.51/2.55 Linear 2.51/2.55 ->Coefficients: 2.51/2.55 Natural Numbers 2.51/2.55 ->Dimension: 2.51/2.55 1 2.51/2.55 ->Bound: 2.51/2.55 2 2.51/2.55 ->Interpretation: 2.51/2.55 2.51/2.55 [0](X) = X + 2 2.51/2.55 [U11](X1,X2,X3) = 0 2.51/2.55 [U12](X1,X2,X3) = 0 2.51/2.55 [U21](X1,X2,X3) = 0 2.51/2.55 [U22](X1,X2,X3) = 0 2.51/2.55 [U31](X1,X2,X3) = X1 + X2 + X3 + 2 2.51/2.55 [U32](X1,X2,X3) = X1 + X2 + X3 + 2 2.51/2.55 [U41](X1,X2,X3) = X1 + X2 + X3 + 2 2.51/2.55 [U42](X1,X2,X3) = X2 + X3 + 2 2.51/2.55 [U51](X1,X2,X3) = X1 + X2 + X3 + 2 2.51/2.55 [U52](X1,X2,X3) = X1 + X2 + X3 + 2 2.51/2.55 [U61](X1,X2,X3) = 0 2.51/2.55 [U62](X1,X2,X3) = 0 2.51/2.55 [U71](X1,X2,X3) = 0 2.51/2.55 [U72](X1,X2,X3) = 0 2.51/2.55 [mult](X1,X2) = 0 2.51/2.55 [plus](X1,X2) = X1 + X2 2.51/2.55 [prod](X) = 0 2.51/2.55 [sum](X) = 0 2.51/2.55 [union](X1,X2) = 0 2.51/2.55 [1](X) = X + 2 2.51/2.55 [empty] = 0 2.51/2.55 [singl](X) = 0 2.51/2.55 [tt] = 2 2.51/2.55 [z] = 0 2.51/2.55 [0#](X) = 0 2.51/2.55 [U11#](X1,X2,X3) = 0 2.51/2.55 [U12#](X1,X2,X3) = 0 2.51/2.55 [U21#](X1,X2,X3) = 0 2.51/2.55 [U22#](X1,X2,X3) = 0 2.51/2.55 [U31#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.55 [U32#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 2.51/2.55 [U41#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 2.51/2.55 [U42#](X1,X2,X3) = X1 + 2.X2 + 2.X3 2.51/2.55 [U51#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.55 [U52#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.55 [U61#](X1,X2,X3) = 0 2.51/2.55 [U62#](X1,X2,X3) = 0 2.51/2.55 [U71#](X1,X2,X3) = 0 2.51/2.55 [U72#](X1,X2,X3) = 0 2.51/2.55 [MULT](X1,X2) = 0 2.51/2.55 [PLUS](X1,X2) = 2.X1 + 2.X2 + 2 2.51/2.55 [PROD](X) = 0 2.51/2.55 [SUM](X) = 0 2.51/2.55 [UNION](X1,X2) = 0 2.51/2.55 2.51/2.55 Problem 1.2: 2.51/2.55 2.51/2.55 SCC Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.55 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 U32#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U41#(tt,X,Y) -> U42#(tt,X,Y) 2.51/2.55 U42#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.55 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.55 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 PLUS(0(X),0(Y)) -> U31#(tt,X,Y) 2.51/2.55 PLUS(0(X),1(Y)) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> U31#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.55 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.55 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.55 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.55 ->Strongly Connected Components: 2.51/2.55 ->->Cycle: 2.51/2.55 ->->-> Pairs: 2.51/2.55 U41#(tt,X,Y) -> U42#(tt,X,Y) 2.51/2.55 U42#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.55 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.55 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 PLUS(0(X),1(Y)) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.55 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.55 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.55 -> FAxioms: 2.51/2.55 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) -> mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) -> plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) -> union(x5,x4) 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,plus(x5,x6)) 2.51/2.55 PLUS(x4,x5) -> PLUS(x5,x4) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 ->->-> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.55 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.55 2.51/2.55 Problem 1.2: 2.51/2.55 2.51/2.55 Reduction Pairs Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.55 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 U41#(tt,X,Y) -> U42#(tt,X,Y) 2.51/2.55 U42#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.55 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.55 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 PLUS(0(X),1(Y)) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.55 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.55 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Usable Equations: 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> Usable Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 -> SRules: 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.55 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.55 ->Interpretation type: 2.51/2.55 Linear 2.51/2.55 ->Coefficients: 2.51/2.55 Natural Numbers 2.51/2.55 ->Dimension: 2.51/2.55 1 2.51/2.55 ->Bound: 2.51/2.55 2 2.51/2.55 ->Interpretation: 2.51/2.55 2.51/2.55 [0](X) = X + 1 2.51/2.55 [U11](X1,X2,X3) = 0 2.51/2.55 [U12](X1,X2,X3) = 0 2.51/2.55 [U21](X1,X2,X3) = 0 2.51/2.55 [U22](X1,X2,X3) = 0 2.51/2.55 [U31](X1,X2,X3) = X2 + X3 + 2 2.51/2.55 [U32](X1,X2,X3) = X2 + X3 + 2 2.51/2.55 [U41](X1,X2,X3) = 2.X1 + X2 + X3 2.51/2.55 [U42](X1,X2,X3) = X1 + X2 + X3 + 2 2.51/2.55 [U51](X1,X2,X3) = 2.X1 + X2 + X3 + 1 2.51/2.55 [U52](X1,X2,X3) = 2.X1 + X2 + X3 + 1 2.51/2.55 [U61](X1,X2,X3) = 0 2.51/2.55 [U62](X1,X2,X3) = 0 2.51/2.55 [U71](X1,X2,X3) = 0 2.51/2.55 [U72](X1,X2,X3) = 0 2.51/2.55 [mult](X1,X2) = 0 2.51/2.55 [plus](X1,X2) = X1 + X2 + 1 2.51/2.55 [prod](X) = 0 2.51/2.55 [sum](X) = 0 2.51/2.55 [union](X1,X2) = 0 2.51/2.55 [1](X) = X + 2 2.51/2.55 [empty] = 0 2.51/2.55 [singl](X) = 0 2.51/2.55 [tt] = 2 2.51/2.55 [z] = 0 2.51/2.55 [0#](X) = 0 2.51/2.55 [U11#](X1,X2,X3) = 0 2.51/2.55 [U12#](X1,X2,X3) = 0 2.51/2.55 [U21#](X1,X2,X3) = 0 2.51/2.55 [U22#](X1,X2,X3) = 0 2.51/2.55 [U31#](X1,X2,X3) = 0 2.51/2.55 [U32#](X1,X2,X3) = 0 2.51/2.55 [U41#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 2.51/2.55 [U42#](X1,X2,X3) = 2.X2 + 2.X3 + 2 2.51/2.55 [U51#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.55 [U52#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.55 [U61#](X1,X2,X3) = 0 2.51/2.55 [U62#](X1,X2,X3) = 0 2.51/2.55 [U71#](X1,X2,X3) = 0 2.51/2.55 [U72#](X1,X2,X3) = 0 2.51/2.55 [MULT](X1,X2) = 0 2.51/2.55 [PLUS](X1,X2) = 2.X1 + 2.X2 2.51/2.55 [PROD](X) = 0 2.51/2.55 [SUM](X) = 0 2.51/2.55 [UNION](X1,X2) = 0 2.51/2.55 2.51/2.55 Problem 1.2: 2.51/2.55 2.51/2.55 SCC Processor: 2.51/2.55 -> FAxioms: 2.51/2.55 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.55 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.55 -> Pairs: 2.51/2.55 U42#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.55 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.55 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 PLUS(0(X),1(Y)) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> U41#(tt,X,Y) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.55 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.55 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.55 -> EAxioms: 2.51/2.55 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) = mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.55 plus(x4,x5) = plus(x5,x4) 2.51/2.55 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.55 union(x4,x5) = union(x5,x4) 2.51/2.55 -> Rules: 2.51/2.55 0(z) -> z 2.51/2.55 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.55 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.55 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.55 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.55 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.55 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.55 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.55 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.55 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.55 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.55 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.55 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.55 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.55 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.55 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.55 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.55 mult(z,X) -> z 2.51/2.55 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.55 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.55 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.55 plus(z,X) -> X 2.51/2.55 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.55 prod(empty) -> 1(z) 2.51/2.55 prod(singl(X)) -> X 2.51/2.55 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.55 sum(empty) -> 0(z) 2.51/2.55 sum(singl(X)) -> X 2.51/2.55 union(empty,X) -> X 2.51/2.55 union(X,empty) -> X 2.51/2.55 -> SRules: 2.51/2.55 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.55 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.55 ->Strongly Connected Components: 2.51/2.55 ->->Cycle: 2.51/2.55 ->->-> Pairs: 2.51/2.55 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.55 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.55 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.55 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.55 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.55 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.55 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.55 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.55 -> FAxioms: 2.51/2.55 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.55 mult(x4,x5) -> mult(x5,x4) 2.51/2.55 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) -> plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) -> union(x5,x4) 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) -> PLUS(x5,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 ->->-> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 Reduction Pairs Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 U51#(tt,X,Y) -> U52#(tt,X,Y) 2.51/2.56 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.56 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.56 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.56 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Usable Equations: 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> Usable Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Interpretation type: 2.51/2.56 Linear 2.51/2.56 ->Coefficients: 2.51/2.56 Natural Numbers 2.51/2.56 ->Dimension: 2.51/2.56 1 2.51/2.56 ->Bound: 2.51/2.56 2 2.51/2.56 ->Interpretation: 2.51/2.56 2.51/2.56 [0](X) = 2.X 2.51/2.56 [U11](X1,X2,X3) = 0 2.51/2.56 [U12](X1,X2,X3) = 0 2.51/2.56 [U21](X1,X2,X3) = 0 2.51/2.56 [U22](X1,X2,X3) = 0 2.51/2.56 [U31](X1,X2,X3) = 2.X2 + 2.X3 2.51/2.56 [U32](X1,X2,X3) = 2.X2 + 2.X3 2.51/2.56 [U41](X1,X2,X3) = 2.X2 + 2.X3 + 2 2.51/2.56 [U42](X1,X2,X3) = 2.X2 + 2.X3 + 2 2.51/2.56 [U51](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.56 [U52](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.56 [U61](X1,X2,X3) = 0 2.51/2.56 [U62](X1,X2,X3) = 0 2.51/2.56 [U71](X1,X2,X3) = 0 2.51/2.56 [U72](X1,X2,X3) = 0 2.51/2.56 [mult](X1,X2) = 0 2.51/2.56 [plus](X1,X2) = X1 + X2 2.51/2.56 [prod](X) = 0 2.51/2.56 [sum](X) = 0 2.51/2.56 [union](X1,X2) = 0 2.51/2.56 [1](X) = 2.X + 2 2.51/2.56 [empty] = 0 2.51/2.56 [singl](X) = 0 2.51/2.56 [tt] = 1 2.51/2.56 [z] = 0 2.51/2.56 [0#](X) = 0 2.51/2.56 [U11#](X1,X2,X3) = 0 2.51/2.56 [U12#](X1,X2,X3) = 0 2.51/2.56 [U21#](X1,X2,X3) = 0 2.51/2.56 [U22#](X1,X2,X3) = 0 2.51/2.56 [U31#](X1,X2,X3) = 0 2.51/2.56 [U32#](X1,X2,X3) = 0 2.51/2.56 [U41#](X1,X2,X3) = 0 2.51/2.56 [U42#](X1,X2,X3) = 0 2.51/2.56 [U51#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.56 [U52#](X1,X2,X3) = X1 + 2.X2 + 2.X3 + 2 2.51/2.56 [U61#](X1,X2,X3) = 0 2.51/2.56 [U62#](X1,X2,X3) = 0 2.51/2.56 [U71#](X1,X2,X3) = 0 2.51/2.56 [U72#](X1,X2,X3) = 0 2.51/2.56 [MULT](X1,X2) = 0 2.51/2.56 [PLUS](X1,X2) = X1 + X2 + 1 2.51/2.56 [PROD](X) = 0 2.51/2.56 [SUM](X) = 0 2.51/2.56 [UNION](X1,X2) = 0 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 SCC Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 U52#(tt,X,Y) -> PLUS(plus(X,Y),1(z)) 2.51/2.56 U52#(tt,X,Y) -> PLUS(X,Y) 2.51/2.56 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.56 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> U51#(tt,X,Y) 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 PLUS(1(X),1(Y)) -> U51#(tt,X,Y) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Strongly Connected Components: 2.51/2.56 ->->Cycle: 2.51/2.56 ->->-> Pairs: 2.51/2.56 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.56 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> FAxioms: 2.51/2.56 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) -> mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) -> plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) -> union(x5,x4) 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) -> PLUS(x5,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 ->->-> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 Reduction Pairs Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 PLUS(plus(0(X),0(Y)),x4) -> PLUS(U31(tt,X,Y),x4) 2.51/2.56 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Usable Equations: 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> Usable Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Interpretation type: 2.51/2.56 Linear 2.51/2.56 ->Coefficients: 2.51/2.56 Natural Numbers 2.51/2.56 ->Dimension: 2.51/2.56 1 2.51/2.56 ->Bound: 2.51/2.56 2 2.51/2.56 ->Interpretation: 2.51/2.56 2.51/2.56 [0](X) = 2 2.51/2.56 [U11](X1,X2,X3) = 0 2.51/2.56 [U12](X1,X2,X3) = 0 2.51/2.56 [U21](X1,X2,X3) = 0 2.51/2.56 [U22](X1,X2,X3) = 0 2.51/2.56 [U31](X1,X2,X3) = X1 + 2 2.51/2.56 [U32](X1,X2,X3) = 2.X1 2.51/2.56 [U41](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U42](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U51](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U52](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U61](X1,X2,X3) = 0 2.51/2.56 [U62](X1,X2,X3) = 0 2.51/2.56 [U71](X1,X2,X3) = 0 2.51/2.56 [U72](X1,X2,X3) = 0 2.51/2.56 [mult](X1,X2) = 0 2.51/2.56 [plus](X1,X2) = X1 + X2 + 2 2.51/2.56 [prod](X) = 0 2.51/2.56 [sum](X) = 0 2.51/2.56 [union](X1,X2) = 0 2.51/2.56 [1](X) = 2 2.51/2.56 [empty] = 0 2.51/2.56 [singl](X) = 0 2.51/2.56 [tt] = 2 2.51/2.56 [z] = 2 2.51/2.56 [0#](X) = 0 2.51/2.56 [U11#](X1,X2,X3) = 0 2.51/2.56 [U12#](X1,X2,X3) = 0 2.51/2.56 [U21#](X1,X2,X3) = 0 2.51/2.56 [U22#](X1,X2,X3) = 0 2.51/2.56 [U31#](X1,X2,X3) = 0 2.51/2.56 [U32#](X1,X2,X3) = 0 2.51/2.56 [U41#](X1,X2,X3) = 0 2.51/2.56 [U42#](X1,X2,X3) = 0 2.51/2.56 [U51#](X1,X2,X3) = 0 2.51/2.56 [U52#](X1,X2,X3) = 0 2.51/2.56 [U61#](X1,X2,X3) = 0 2.51/2.56 [U62#](X1,X2,X3) = 0 2.51/2.56 [U71#](X1,X2,X3) = 0 2.51/2.56 [U72#](X1,X2,X3) = 0 2.51/2.56 [MULT](X1,X2) = 0 2.51/2.56 [PLUS](X1,X2) = 2.X1 + 2.X2 2.51/2.56 [PROD](X) = 0 2.51/2.56 [SUM](X) = 0 2.51/2.56 [UNION](X1,X2) = 0 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 SCC Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Strongly Connected Components: 2.51/2.56 ->->Cycle: 2.51/2.56 ->->-> Pairs: 2.51/2.56 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> FAxioms: 2.51/2.56 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) -> mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) -> plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) -> union(x5,x4) 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) -> PLUS(x5,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 ->->-> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 Reduction Pairs Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 PLUS(plus(0(X),1(Y)),x4) -> PLUS(U41(tt,X,Y),x4) 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Usable Equations: 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> Usable Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Interpretation type: 2.51/2.56 Linear 2.51/2.56 ->Coefficients: 2.51/2.56 Natural Numbers 2.51/2.56 ->Dimension: 2.51/2.56 1 2.51/2.56 ->Bound: 2.51/2.56 2 2.51/2.56 ->Interpretation: 2.51/2.56 2.51/2.56 [0](X) = 2 2.51/2.56 [U11](X1,X2,X3) = 0 2.51/2.56 [U12](X1,X2,X3) = 0 2.51/2.56 [U21](X1,X2,X3) = 0 2.51/2.56 [U22](X1,X2,X3) = 0 2.51/2.56 [U31](X1,X2,X3) = X1 + 1 2.51/2.56 [U32](X1,X2,X3) = 2 2.51/2.56 [U41](X1,X2,X3) = 2.X1 2.51/2.56 [U42](X1,X2,X3) = X1 + 2 2.51/2.56 [U51](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U52](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U61](X1,X2,X3) = 0 2.51/2.56 [U62](X1,X2,X3) = 0 2.51/2.56 [U71](X1,X2,X3) = 0 2.51/2.56 [U72](X1,X2,X3) = 0 2.51/2.56 [mult](X1,X2) = 0 2.51/2.56 [plus](X1,X2) = X1 + X2 + 2 2.51/2.56 [prod](X) = 0 2.51/2.56 [sum](X) = 0 2.51/2.56 [union](X1,X2) = 0 2.51/2.56 [1](X) = 2 2.51/2.56 [empty] = 0 2.51/2.56 [singl](X) = 0 2.51/2.56 [tt] = 2 2.51/2.56 [z] = 2 2.51/2.56 [0#](X) = 0 2.51/2.56 [U11#](X1,X2,X3) = 0 2.51/2.56 [U12#](X1,X2,X3) = 0 2.51/2.56 [U21#](X1,X2,X3) = 0 2.51/2.56 [U22#](X1,X2,X3) = 0 2.51/2.56 [U31#](X1,X2,X3) = 0 2.51/2.56 [U32#](X1,X2,X3) = 0 2.51/2.56 [U41#](X1,X2,X3) = 0 2.51/2.56 [U42#](X1,X2,X3) = 0 2.51/2.56 [U51#](X1,X2,X3) = 0 2.51/2.56 [U52#](X1,X2,X3) = 0 2.51/2.56 [U61#](X1,X2,X3) = 0 2.51/2.56 [U62#](X1,X2,X3) = 0 2.51/2.56 [U71#](X1,X2,X3) = 0 2.51/2.56 [U72#](X1,X2,X3) = 0 2.51/2.56 [MULT](X1,X2) = 0 2.51/2.56 [PLUS](X1,X2) = 2.X1 + 2.X2 2.51/2.56 [PROD](X) = 0 2.51/2.56 [SUM](X) = 0 2.51/2.56 [UNION](X1,X2) = 0 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 SCC Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Strongly Connected Components: 2.51/2.56 ->->Cycle: 2.51/2.56 ->->-> Pairs: 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> FAxioms: 2.51/2.56 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) -> mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) -> plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) -> union(x5,x4) 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) -> PLUS(x5,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 ->->-> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 Reduction Pairs Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 PLUS(plus(1(X),1(Y)),x4) -> PLUS(U51(tt,X,Y),x4) 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Usable Equations: 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> Usable Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Interpretation type: 2.51/2.56 Linear 2.51/2.56 ->Coefficients: 2.51/2.56 Natural Numbers 2.51/2.56 ->Dimension: 2.51/2.56 1 2.51/2.56 ->Bound: 2.51/2.56 2 2.51/2.56 ->Interpretation: 2.51/2.56 2.51/2.56 [0](X) = 2 2.51/2.56 [U11](X1,X2,X3) = 0 2.51/2.56 [U12](X1,X2,X3) = 0 2.51/2.56 [U21](X1,X2,X3) = 0 2.51/2.56 [U22](X1,X2,X3) = 0 2.51/2.56 [U31](X1,X2,X3) = 2.X1 + 1 2.51/2.56 [U32](X1,X2,X3) = X1 + 2 2.51/2.56 [U41](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U42](X1,X2,X3) = X1 + 1 2.51/2.56 [U51](X1,X2,X3) = X1 + 2 2.51/2.56 [U52](X1,X2,X3) = X1 + 2 2.51/2.56 [U61](X1,X2,X3) = 0 2.51/2.56 [U62](X1,X2,X3) = 0 2.51/2.56 [U71](X1,X2,X3) = 0 2.51/2.56 [U72](X1,X2,X3) = 0 2.51/2.56 [mult](X1,X2) = 0 2.51/2.56 [plus](X1,X2) = X1 + X2 + 2 2.51/2.56 [prod](X) = 0 2.51/2.56 [sum](X) = 0 2.51/2.56 [union](X1,X2) = 0 2.51/2.56 [1](X) = 2 2.51/2.56 [empty] = 0 2.51/2.56 [singl](X) = 0 2.51/2.56 [tt] = 2 2.51/2.56 [z] = 2 2.51/2.56 [0#](X) = 0 2.51/2.56 [U11#](X1,X2,X3) = 0 2.51/2.56 [U12#](X1,X2,X3) = 0 2.51/2.56 [U21#](X1,X2,X3) = 0 2.51/2.56 [U22#](X1,X2,X3) = 0 2.51/2.56 [U31#](X1,X2,X3) = 0 2.51/2.56 [U32#](X1,X2,X3) = 0 2.51/2.56 [U41#](X1,X2,X3) = 0 2.51/2.56 [U42#](X1,X2,X3) = 0 2.51/2.56 [U51#](X1,X2,X3) = 0 2.51/2.56 [U52#](X1,X2,X3) = 0 2.51/2.56 [U61#](X1,X2,X3) = 0 2.51/2.56 [U62#](X1,X2,X3) = 0 2.51/2.56 [U71#](X1,X2,X3) = 0 2.51/2.56 [U72#](X1,X2,X3) = 0 2.51/2.56 [MULT](X1,X2) = 0 2.51/2.56 [PLUS](X1,X2) = 2.X1 + 2.X2 2.51/2.56 [PROD](X) = 0 2.51/2.56 [SUM](X) = 0 2.51/2.56 [UNION](X1,X2) = 0 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 SCC Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Strongly Connected Components: 2.51/2.56 ->->Cycle: 2.51/2.56 ->->-> Pairs: 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> FAxioms: 2.51/2.56 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) -> mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) -> plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) -> union(x5,x4) 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) -> PLUS(x5,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 ->->-> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 Reduction Pairs Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 PLUS(plus(z,X),x4) -> PLUS(X,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Usable Equations: 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> Usable Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Interpretation type: 2.51/2.56 Linear 2.51/2.56 ->Coefficients: 2.51/2.56 Natural Numbers 2.51/2.56 ->Dimension: 2.51/2.56 1 2.51/2.56 ->Bound: 2.51/2.56 2 2.51/2.56 ->Interpretation: 2.51/2.56 2.51/2.56 [0](X) = 2 2.51/2.56 [U11](X1,X2,X3) = 0 2.51/2.56 [U12](X1,X2,X3) = 0 2.51/2.56 [U21](X1,X2,X3) = 0 2.51/2.56 [U22](X1,X2,X3) = 0 2.51/2.56 [U31](X1,X2,X3) = X1 + 2 2.51/2.56 [U32](X1,X2,X3) = 2 2.51/2.56 [U41](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U42](X1,X2,X3) = X1 + 2 2.51/2.56 [U51](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U52](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U61](X1,X2,X3) = 0 2.51/2.56 [U62](X1,X2,X3) = 0 2.51/2.56 [U71](X1,X2,X3) = 0 2.51/2.56 [U72](X1,X2,X3) = 0 2.51/2.56 [mult](X1,X2) = 0 2.51/2.56 [plus](X1,X2) = X1 + X2 + 2 2.51/2.56 [prod](X) = 0 2.51/2.56 [sum](X) = 0 2.51/2.56 [union](X1,X2) = 0 2.51/2.56 [1](X) = 2 2.51/2.56 [empty] = 0 2.51/2.56 [singl](X) = 0 2.51/2.56 [tt] = 0 2.51/2.56 [z] = 0 2.51/2.56 [0#](X) = 0 2.51/2.56 [U11#](X1,X2,X3) = 0 2.51/2.56 [U12#](X1,X2,X3) = 0 2.51/2.56 [U21#](X1,X2,X3) = 0 2.51/2.56 [U22#](X1,X2,X3) = 0 2.51/2.56 [U31#](X1,X2,X3) = 0 2.51/2.56 [U32#](X1,X2,X3) = 0 2.51/2.56 [U41#](X1,X2,X3) = 0 2.51/2.56 [U42#](X1,X2,X3) = 0 2.51/2.56 [U51#](X1,X2,X3) = 0 2.51/2.56 [U52#](X1,X2,X3) = 0 2.51/2.56 [U61#](X1,X2,X3) = 0 2.51/2.56 [U62#](X1,X2,X3) = 0 2.51/2.56 [U71#](X1,X2,X3) = 0 2.51/2.56 [U72#](X1,X2,X3) = 0 2.51/2.56 [MULT](X1,X2) = 0 2.51/2.56 [PLUS](X1,X2) = 2.X1 + 2.X2 2.51/2.56 [PROD](X) = 0 2.51/2.56 [SUM](X) = 0 2.51/2.56 [UNION](X1,X2) = 0 2.51/2.56 2.51/2.56 Problem 1.2: 2.51/2.56 2.51/2.56 SCC Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 PLUS(plus(x4,x5),x6) = PLUS(x4,plus(x5,x6)) 2.51/2.56 PLUS(x4,x5) = PLUS(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 Empty 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 PLUS(plus(x4,x5),x6) -> PLUS(x4,x5) 2.51/2.56 PLUS(x4,plus(x5,x6)) -> PLUS(x5,x6) 2.51/2.56 ->Strongly Connected Components: 2.51/2.56 There is no strongly connected component 2.51/2.56 2.51/2.56 The problem is finite. 2.51/2.56 2.51/2.56 Problem 1.3: 2.51/2.56 2.51/2.56 Reduction Pairs Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 Empty 2.51/2.56 -> Pairs: 2.51/2.56 U71#(tt,A,B) -> U72#(tt,A,B) 2.51/2.56 U72#(tt,A,B) -> SUM(A) 2.51/2.56 U72#(tt,A,B) -> SUM(B) 2.51/2.56 SUM(union(A,B)) -> U71#(tt,A,B) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Usable Equations: 2.51/2.56 Empty 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> Usable Rules: 2.51/2.56 Empty 2.51/2.56 -> SRules: 2.51/2.56 Empty 2.51/2.56 ->Interpretation type: 2.51/2.56 Linear 2.51/2.56 ->Coefficients: 2.51/2.56 Natural Numbers 2.51/2.56 ->Dimension: 2.51/2.56 1 2.51/2.56 ->Bound: 2.51/2.56 2 2.51/2.56 ->Interpretation: 2.51/2.56 2.51/2.56 [0](X) = 0 2.51/2.56 [U11](X1,X2,X3) = 0 2.51/2.56 [U12](X1,X2,X3) = 0 2.51/2.56 [U21](X1,X2,X3) = 0 2.51/2.56 [U22](X1,X2,X3) = 0 2.51/2.56 [U31](X1,X2,X3) = 0 2.51/2.56 [U32](X1,X2,X3) = 0 2.51/2.56 [U41](X1,X2,X3) = 0 2.51/2.56 [U42](X1,X2,X3) = 0 2.51/2.56 [U51](X1,X2,X3) = 0 2.51/2.56 [U52](X1,X2,X3) = 0 2.51/2.56 [U61](X1,X2,X3) = 0 2.51/2.56 [U62](X1,X2,X3) = 0 2.51/2.56 [U71](X1,X2,X3) = 0 2.51/2.56 [U72](X1,X2,X3) = 0 2.51/2.56 [mult](X1,X2) = 0 2.51/2.56 [plus](X1,X2) = 0 2.51/2.56 [prod](X) = 0 2.51/2.56 [sum](X) = 0 2.51/2.56 [union](X1,X2) = 2.X1 + 2.X2 + 2 2.51/2.56 [1](X) = 0 2.51/2.56 [empty] = 0 2.51/2.56 [singl](X) = 0 2.51/2.56 [tt] = 0 2.51/2.56 [z] = 0 2.51/2.56 [0#](X) = 0 2.51/2.56 [U11#](X1,X2,X3) = 0 2.51/2.56 [U12#](X1,X2,X3) = 0 2.51/2.56 [U21#](X1,X2,X3) = 0 2.51/2.56 [U22#](X1,X2,X3) = 0 2.51/2.56 [U31#](X1,X2,X3) = 0 2.51/2.56 [U32#](X1,X2,X3) = 0 2.51/2.56 [U41#](X1,X2,X3) = 0 2.51/2.56 [U42#](X1,X2,X3) = 0 2.51/2.56 [U51#](X1,X2,X3) = 0 2.51/2.56 [U52#](X1,X2,X3) = 0 2.51/2.56 [U61#](X1,X2,X3) = 0 2.51/2.56 [U62#](X1,X2,X3) = 0 2.51/2.56 [U71#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.56 [U72#](X1,X2,X3) = 2.X2 + 2.X3 2.51/2.56 [MULT](X1,X2) = 0 2.51/2.56 [PLUS](X1,X2) = 0 2.51/2.56 [PROD](X) = 0 2.51/2.56 [SUM](X) = 2.X 2.51/2.56 [UNION](X1,X2) = 0 2.51/2.56 2.51/2.56 Problem 1.3: 2.51/2.56 2.51/2.56 SCC Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 Empty 2.51/2.56 -> Pairs: 2.51/2.56 U72#(tt,A,B) -> SUM(A) 2.51/2.56 U72#(tt,A,B) -> SUM(B) 2.51/2.56 SUM(union(A,B)) -> U71#(tt,A,B) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 Empty 2.51/2.56 ->Strongly Connected Components: 2.51/2.56 There is no strongly connected component 2.51/2.56 2.51/2.56 The problem is finite. 2.51/2.56 2.51/2.56 Problem 1.4: 2.51/2.56 2.51/2.56 Reduction Pairs Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.56 MULT(x4,x5) = MULT(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 U11#(tt,X,Y) -> U12#(tt,X,Y) 2.51/2.56 U12#(tt,X,Y) -> MULT(X,Y) 2.51/2.56 U21#(tt,X,Y) -> U22#(tt,X,Y) 2.51/2.56 U22#(tt,X,Y) -> MULT(X,Y) 2.51/2.56 MULT(0(X),Y) -> U11#(tt,X,Y) 2.51/2.56 MULT(mult(0(X),Y),x4) -> U11#(tt,X,Y) 2.51/2.56 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.56 MULT(mult(1(X),Y),x4) -> U21#(tt,X,Y) 2.51/2.56 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.56 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.56 MULT(1(X),Y) -> U21#(tt,X,Y) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Usable Equations: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> Usable Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 -> SRules: 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.56 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.56 ->Interpretation type: 2.51/2.56 Simple mixed 2.51/2.56 ->Coefficients: 2.51/2.56 Natural Numbers 2.51/2.56 ->Dimension: 2.51/2.56 1 2.51/2.56 ->Bound: 2.51/2.56 1 2.51/2.56 ->Interpretation: 2.51/2.56 2.51/2.56 [0](X) = X + 1 2.51/2.56 [U11](X1,X2,X3) = X1.X2.X3 + X1.X3 + X1 + X2 + X3 2.51/2.56 [U12](X1,X2,X3) = X1.X2.X3 + X1.X3 + X2 + 1 2.51/2.56 [U21](X1,X2,X3) = X1.X3 + X2.X3 + X2 + X3 + 1 2.51/2.56 [U22](X1,X2,X3) = X1.X2.X3 + X1.X3 + X2 + X3 + 1 2.51/2.56 [U31](X1,X2,X3) = X1.X2 + X1.X3 + 1 2.51/2.56 [U32](X1,X2,X3) = X1.X3 + X2 + 1 2.51/2.56 [U41](X1,X2,X3) = X1.X2 + X1.X3 + X1 + 1 2.51/2.56 [U42](X1,X2,X3) = X1.X3 + X2 + 1 2.51/2.56 [U51](X1,X2,X3) = X1.X3 + X1 + X2 + 1 2.51/2.56 [U52](X1,X2,X3) = X1.X3 + X1 + X2 + 1 2.51/2.56 [U61](X1,X2,X3) = 0 2.51/2.56 [U62](X1,X2,X3) = 0 2.51/2.56 [U71](X1,X2,X3) = 0 2.51/2.56 [U72](X1,X2,X3) = 0 2.51/2.56 [mult](X1,X2) = X1.X2 + X1 + X2 2.51/2.56 [plus](X1,X2) = X1 + X2 2.51/2.56 [prod](X) = 0 2.51/2.56 [sum](X) = 0 2.51/2.56 [union](X1,X2) = 0 2.51/2.56 [1](X) = X + 1 2.51/2.56 [empty] = 0 2.51/2.56 [singl](X) = 0 2.51/2.56 [tt] = 1 2.51/2.56 [z] = 0 2.51/2.56 [0#](X) = 0 2.51/2.56 [U11#](X1,X2,X3) = X2.X3 + X1 + X2 + X3 + 1 2.51/2.56 [U12#](X1,X2,X3) = X2.X3 + X2 + X3 + 1 2.51/2.56 [U21#](X1,X2,X3) = X1.X2.X3 + X1.X3 + X2 + 1 2.51/2.56 [U22#](X1,X2,X3) = X1.X2 + X2.X3 + X3 + 1 2.51/2.56 [U31#](X1,X2,X3) = 0 2.51/2.56 [U32#](X1,X2,X3) = 0 2.51/2.56 [U41#](X1,X2,X3) = 0 2.51/2.56 [U42#](X1,X2,X3) = 0 2.51/2.56 [U51#](X1,X2,X3) = 0 2.51/2.56 [U52#](X1,X2,X3) = 0 2.51/2.56 [U61#](X1,X2,X3) = 0 2.51/2.56 [U62#](X1,X2,X3) = 0 2.51/2.56 [U71#](X1,X2,X3) = 0 2.51/2.56 [U72#](X1,X2,X3) = 0 2.51/2.56 [MULT](X1,X2) = X1.X2 + X1 + X2 + 1 2.51/2.56 [PLUS](X1,X2) = 0 2.51/2.56 [PROD](X) = 0 2.51/2.56 [SUM](X) = 0 2.51/2.56 [UNION](X1,X2) = 0 2.51/2.56 2.51/2.56 Problem 1.4: 2.51/2.56 2.51/2.56 SCC Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.56 MULT(x4,x5) = MULT(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 U12#(tt,X,Y) -> MULT(X,Y) 2.51/2.56 U21#(tt,X,Y) -> U22#(tt,X,Y) 2.51/2.56 U22#(tt,X,Y) -> MULT(X,Y) 2.51/2.56 MULT(0(X),Y) -> U11#(tt,X,Y) 2.51/2.56 MULT(mult(0(X),Y),x4) -> U11#(tt,X,Y) 2.51/2.56 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.56 MULT(mult(1(X),Y),x4) -> U21#(tt,X,Y) 2.51/2.56 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.56 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.56 MULT(1(X),Y) -> U21#(tt,X,Y) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.56 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.56 ->Strongly Connected Components: 2.51/2.56 ->->Cycle: 2.51/2.56 ->->-> Pairs: 2.51/2.56 U21#(tt,X,Y) -> U22#(tt,X,Y) 2.51/2.56 U22#(tt,X,Y) -> MULT(X,Y) 2.51/2.56 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.56 MULT(mult(1(X),Y),x4) -> U21#(tt,X,Y) 2.51/2.56 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.56 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.56 MULT(1(X),Y) -> U21#(tt,X,Y) 2.51/2.56 -> FAxioms: 2.51/2.56 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) -> mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) -> plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) -> union(x5,x4) 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,mult(x5,x6)) 2.51/2.56 MULT(x4,x5) -> MULT(x5,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 ->->-> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.56 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.56 2.51/2.56 Problem 1.4: 2.51/2.56 2.51/2.56 Reduction Pairs Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.56 MULT(x4,x5) = MULT(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 U21#(tt,X,Y) -> U22#(tt,X,Y) 2.51/2.56 U22#(tt,X,Y) -> MULT(X,Y) 2.51/2.56 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.56 MULT(mult(1(X),Y),x4) -> U21#(tt,X,Y) 2.51/2.56 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.56 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.56 MULT(1(X),Y) -> U21#(tt,X,Y) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Usable Equations: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> Usable Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 -> SRules: 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.56 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.56 ->Interpretation type: 2.51/2.56 Simple mixed 2.51/2.56 ->Coefficients: 2.51/2.56 Natural Numbers 2.51/2.56 ->Dimension: 2.51/2.56 1 2.51/2.56 ->Bound: 2.51/2.56 1 2.51/2.56 ->Interpretation: 2.51/2.56 2.51/2.56 [0](X) = X + 1 2.51/2.56 [U11](X1,X2,X3) = X1.X2 + X2.X3 + X3 + 1 2.51/2.56 [U12](X1,X2,X3) = X1.X2.X3 + X1.X2 + X1.X3 + 1 2.51/2.56 [U21](X1,X2,X3) = X1.X3 + X2.X3 + X2 + X3 + 1 2.51/2.56 [U22](X1,X2,X3) = X1.X2.X3 + X1.X2 + X1.X3 + X1 + X3 2.51/2.56 [U31](X1,X2,X3) = X1 + X2 + X3 + 1 2.51/2.56 [U32](X1,X2,X3) = X1 + X2 + X3 + 1 2.51/2.56 [U41](X1,X2,X3) = X1.X2 + X1 + X3 2.51/2.56 [U42](X1,X2,X3) = X1.X3 + X1 + X2 2.51/2.56 [U51](X1,X2,X3) = X1.X2 + X1.X3 + X1 + 1 2.51/2.56 [U52](X1,X2,X3) = X1.X3 + X1 + X2 + 1 2.51/2.56 [U61](X1,X2,X3) = 0 2.51/2.56 [U62](X1,X2,X3) = 0 2.51/2.56 [U71](X1,X2,X3) = 0 2.51/2.56 [U72](X1,X2,X3) = 0 2.51/2.56 [mult](X1,X2) = X1.X2 + X1 + X2 2.51/2.56 [plus](X1,X2) = X1 + X2 2.51/2.56 [prod](X) = 0 2.51/2.56 [sum](X) = 0 2.51/2.56 [union](X1,X2) = 0 2.51/2.56 [1](X) = X + 1 2.51/2.56 [empty] = 0 2.51/2.56 [singl](X) = 0 2.51/2.56 [tt] = 1 2.51/2.56 [z] = 0 2.51/2.56 [0#](X) = 0 2.51/2.56 [U11#](X1,X2,X3) = 0 2.51/2.56 [U12#](X1,X2,X3) = 0 2.51/2.56 [U21#](X1,X2,X3) = X1.X2.X3 + X1.X3 + X1 + X2 + X3 + 1 2.51/2.56 [U22#](X1,X2,X3) = X1.X2 + X1.X3 + X2.X3 + X3 + 1 2.51/2.56 [U31#](X1,X2,X3) = 0 2.51/2.56 [U32#](X1,X2,X3) = 0 2.51/2.56 [U41#](X1,X2,X3) = 0 2.51/2.56 [U42#](X1,X2,X3) = 0 2.51/2.56 [U51#](X1,X2,X3) = 0 2.51/2.56 [U52#](X1,X2,X3) = 0 2.51/2.56 [U61#](X1,X2,X3) = 0 2.51/2.56 [U62#](X1,X2,X3) = 0 2.51/2.56 [U71#](X1,X2,X3) = 0 2.51/2.56 [U72#](X1,X2,X3) = 0 2.51/2.56 [MULT](X1,X2) = X1.X2 + X1 + X2 + 1 2.51/2.56 [PLUS](X1,X2) = 0 2.51/2.56 [PROD](X) = 0 2.51/2.56 [SUM](X) = 0 2.51/2.56 [UNION](X1,X2) = 0 2.51/2.56 2.51/2.56 Problem 1.4: 2.51/2.56 2.51/2.56 SCC Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.56 MULT(x4,x5) = MULT(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 U22#(tt,X,Y) -> MULT(X,Y) 2.51/2.56 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.56 MULT(mult(1(X),Y),x4) -> U21#(tt,X,Y) 2.51/2.56 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.56 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.56 MULT(1(X),Y) -> U21#(tt,X,Y) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.56 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.56 ->Strongly Connected Components: 2.51/2.56 ->->Cycle: 2.51/2.56 ->->-> Pairs: 2.51/2.56 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.56 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.56 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.56 -> FAxioms: 2.51/2.56 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) -> mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) -> plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) -> union(x5,x4) 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,mult(x5,x6)) 2.51/2.56 MULT(x4,x5) -> MULT(x5,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 ->->-> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.56 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.56 2.51/2.56 Problem 1.4: 2.51/2.56 2.51/2.56 Reduction Pairs Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.56 MULT(x4,x5) = MULT(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 MULT(mult(0(X),Y),x4) -> MULT(U11(tt,X,Y),x4) 2.51/2.56 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.56 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Usable Equations: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> Usable Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 -> SRules: 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.56 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.56 ->Interpretation type: 2.51/2.56 Linear 2.51/2.56 ->Coefficients: 2.51/2.56 Natural Numbers 2.51/2.56 ->Dimension: 2.51/2.56 1 2.51/2.56 ->Bound: 2.51/2.56 2 2.51/2.56 ->Interpretation: 2.51/2.56 2.51/2.56 [0](X) = 2 2.51/2.56 [U11](X1,X2,X3) = X3 + 2 2.51/2.56 [U12](X1,X2,X3) = X3 + 2 2.51/2.56 [U21](X1,X2,X3) = X1 + X3 + 2 2.51/2.56 [U22](X1,X2,X3) = 2.X1 + X3 2.51/2.56 [U31](X1,X2,X3) = 2.X1 + 1 2.51/2.56 [U32](X1,X2,X3) = X1 + 2 2.51/2.56 [U41](X1,X2,X3) = 2 2.51/2.56 [U42](X1,X2,X3) = 2 2.51/2.56 [U51](X1,X2,X3) = 2.X1 + 2 2.51/2.56 [U52](X1,X2,X3) = 2 2.51/2.56 [U61](X1,X2,X3) = 0 2.51/2.56 [U62](X1,X2,X3) = 0 2.51/2.56 [U71](X1,X2,X3) = 0 2.51/2.56 [U72](X1,X2,X3) = 0 2.51/2.56 [mult](X1,X2) = X1 + X2 + 2 2.51/2.56 [plus](X1,X2) = X1 + X2 + 2 2.51/2.56 [prod](X) = 0 2.51/2.56 [sum](X) = 0 2.51/2.56 [union](X1,X2) = 0 2.51/2.56 [1](X) = 2 2.51/2.56 [empty] = 0 2.51/2.56 [singl](X) = 0 2.51/2.56 [tt] = 2 2.51/2.56 [z] = 1 2.51/2.56 [0#](X) = 0 2.51/2.56 [U11#](X1,X2,X3) = 0 2.51/2.56 [U12#](X1,X2,X3) = 0 2.51/2.56 [U21#](X1,X2,X3) = 0 2.51/2.56 [U22#](X1,X2,X3) = 0 2.51/2.56 [U31#](X1,X2,X3) = 0 2.51/2.56 [U32#](X1,X2,X3) = 0 2.51/2.56 [U41#](X1,X2,X3) = 0 2.51/2.56 [U42#](X1,X2,X3) = 0 2.51/2.56 [U51#](X1,X2,X3) = 0 2.51/2.56 [U52#](X1,X2,X3) = 0 2.51/2.56 [U61#](X1,X2,X3) = 0 2.51/2.56 [U62#](X1,X2,X3) = 0 2.51/2.56 [U71#](X1,X2,X3) = 0 2.51/2.56 [U72#](X1,X2,X3) = 0 2.51/2.56 [MULT](X1,X2) = 2.X1 + 2.X2 2.51/2.56 [PLUS](X1,X2) = 0 2.51/2.56 [PROD](X) = 0 2.51/2.56 [SUM](X) = 0 2.51/2.56 [UNION](X1,X2) = 0 2.51/2.56 2.51/2.56 Problem 1.4: 2.51/2.56 2.51/2.56 SCC Processor: 2.51/2.56 -> FAxioms: 2.51/2.56 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.56 MULT(x4,x5) = MULT(x5,x4) 2.51/2.56 -> Pairs: 2.51/2.56 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.56 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 -> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.56 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.56 plus(z,X) -> X 2.51/2.56 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.56 prod(empty) -> 1(z) 2.51/2.56 prod(singl(X)) -> X 2.51/2.56 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.56 sum(empty) -> 0(z) 2.51/2.56 sum(singl(X)) -> X 2.51/2.56 union(empty,X) -> X 2.51/2.56 union(X,empty) -> X 2.51/2.56 -> SRules: 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.56 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.56 ->Strongly Connected Components: 2.51/2.56 ->->Cycle: 2.51/2.56 ->->-> Pairs: 2.51/2.56 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.56 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.56 -> FAxioms: 2.51/2.56 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) -> mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) -> plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) -> union(x5,x4) 2.51/2.56 MULT(mult(x4,x5),x6) -> MULT(x4,mult(x5,x6)) 2.51/2.56 MULT(x4,x5) -> MULT(x5,x4) 2.51/2.56 -> EAxioms: 2.51/2.56 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.56 mult(x4,x5) = mult(x5,x4) 2.51/2.56 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.56 plus(x4,x5) = plus(x5,x4) 2.51/2.56 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.56 union(x4,x5) = union(x5,x4) 2.51/2.56 ->->-> Rules: 2.51/2.56 0(z) -> z 2.51/2.56 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.56 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.56 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.56 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.56 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.56 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.56 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.56 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.56 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.56 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.56 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.56 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.56 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.56 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.56 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.56 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.56 mult(z,X) -> z 2.51/2.56 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.56 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.57 prod(empty) -> 1(z) 2.51/2.57 prod(singl(X)) -> X 2.51/2.57 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.57 sum(empty) -> 0(z) 2.51/2.57 sum(singl(X)) -> X 2.51/2.57 union(empty,X) -> X 2.51/2.57 union(X,empty) -> X 2.51/2.57 -> SRules: 2.51/2.57 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.57 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.57 2.51/2.57 Problem 1.4: 2.51/2.57 2.51/2.57 Reduction Pairs Processor: 2.51/2.57 -> FAxioms: 2.51/2.57 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.57 MULT(x4,x5) = MULT(x5,x4) 2.51/2.57 -> Pairs: 2.51/2.57 MULT(mult(1(X),Y),x4) -> MULT(U21(tt,X,Y),x4) 2.51/2.57 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.57 -> EAxioms: 2.51/2.57 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) = mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) = plus(x5,x4) 2.51/2.57 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.57 union(x4,x5) = union(x5,x4) 2.51/2.57 -> Usable Equations: 2.51/2.57 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) = mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) = plus(x5,x4) 2.51/2.57 -> Rules: 2.51/2.57 0(z) -> z 2.51/2.57 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.57 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.57 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.57 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.57 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.57 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.57 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.57 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.57 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.57 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.57 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.57 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.57 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.57 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.57 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.57 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.57 mult(z,X) -> z 2.51/2.57 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.57 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.57 prod(empty) -> 1(z) 2.51/2.57 prod(singl(X)) -> X 2.51/2.57 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.57 sum(empty) -> 0(z) 2.51/2.57 sum(singl(X)) -> X 2.51/2.57 union(empty,X) -> X 2.51/2.57 union(X,empty) -> X 2.51/2.57 -> Usable Rules: 2.51/2.57 0(z) -> z 2.51/2.57 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.57 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.57 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.57 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.57 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.57 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.57 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.57 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.57 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.57 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.57 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.57 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.57 mult(z,X) -> z 2.51/2.57 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.57 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 -> SRules: 2.51/2.57 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.57 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.57 ->Interpretation type: 2.51/2.57 Linear 2.51/2.57 ->Coefficients: 2.51/2.57 Natural Numbers 2.51/2.57 ->Dimension: 2.51/2.57 1 2.51/2.57 ->Bound: 2.51/2.57 2 2.51/2.57 ->Interpretation: 2.51/2.57 2.51/2.57 [0](X) = 2 2.51/2.57 [U11](X1,X2,X3) = 2 2.51/2.57 [U12](X1,X2,X3) = 2 2.51/2.57 [U21](X1,X2,X3) = X1 + X3 2.51/2.57 [U22](X1,X2,X3) = X3 + 2 2.51/2.57 [U31](X1,X2,X3) = 2.X1 2.51/2.57 [U32](X1,X2,X3) = X1 + 2 2.51/2.57 [U41](X1,X2,X3) = 2.X1 2.51/2.57 [U42](X1,X2,X3) = X1 + 2 2.51/2.57 [U51](X1,X2,X3) = 2.X1 2.51/2.57 [U52](X1,X2,X3) = 2.X1 2.51/2.57 [U61](X1,X2,X3) = 0 2.51/2.57 [U62](X1,X2,X3) = 0 2.51/2.57 [U71](X1,X2,X3) = 0 2.51/2.57 [U72](X1,X2,X3) = 0 2.51/2.57 [mult](X1,X2) = X1 + X2 + 1 2.51/2.57 [plus](X1,X2) = X1 + X2 2.51/2.57 [prod](X) = 0 2.51/2.57 [sum](X) = 0 2.51/2.57 [union](X1,X2) = 0 2.51/2.57 [1](X) = 2 2.51/2.57 [empty] = 0 2.51/2.57 [singl](X) = 0 2.51/2.57 [tt] = 2 2.51/2.57 [z] = 2 2.51/2.57 [0#](X) = 0 2.51/2.57 [U11#](X1,X2,X3) = 0 2.51/2.57 [U12#](X1,X2,X3) = 0 2.51/2.57 [U21#](X1,X2,X3) = 0 2.51/2.57 [U22#](X1,X2,X3) = 0 2.51/2.57 [U31#](X1,X2,X3) = 0 2.51/2.57 [U32#](X1,X2,X3) = 0 2.51/2.57 [U41#](X1,X2,X3) = 0 2.51/2.57 [U42#](X1,X2,X3) = 0 2.51/2.57 [U51#](X1,X2,X3) = 0 2.51/2.57 [U52#](X1,X2,X3) = 0 2.51/2.57 [U61#](X1,X2,X3) = 0 2.51/2.57 [U62#](X1,X2,X3) = 0 2.51/2.57 [U71#](X1,X2,X3) = 0 2.51/2.57 [U72#](X1,X2,X3) = 0 2.51/2.57 [MULT](X1,X2) = 2.X1 + 2.X2 2.51/2.57 [PLUS](X1,X2) = 0 2.51/2.57 [PROD](X) = 0 2.51/2.57 [SUM](X) = 0 2.51/2.57 [UNION](X1,X2) = 0 2.51/2.57 2.51/2.57 Problem 1.4: 2.51/2.57 2.51/2.57 SCC Processor: 2.51/2.57 -> FAxioms: 2.51/2.57 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.57 MULT(x4,x5) = MULT(x5,x4) 2.51/2.57 -> Pairs: 2.51/2.57 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.57 -> EAxioms: 2.51/2.57 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) = mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) = plus(x5,x4) 2.51/2.57 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.57 union(x4,x5) = union(x5,x4) 2.51/2.57 -> Rules: 2.51/2.57 0(z) -> z 2.51/2.57 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.57 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.57 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.57 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.57 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.57 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.57 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.57 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.57 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.57 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.57 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.57 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.57 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.57 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.57 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.57 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.57 mult(z,X) -> z 2.51/2.57 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.57 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.57 prod(empty) -> 1(z) 2.51/2.57 prod(singl(X)) -> X 2.51/2.57 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.57 sum(empty) -> 0(z) 2.51/2.57 sum(singl(X)) -> X 2.51/2.57 union(empty,X) -> X 2.51/2.57 union(X,empty) -> X 2.51/2.57 -> SRules: 2.51/2.57 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.57 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.57 ->Strongly Connected Components: 2.51/2.57 ->->Cycle: 2.51/2.57 ->->-> Pairs: 2.51/2.57 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.57 -> FAxioms: 2.51/2.57 mult(mult(x4,x5),x6) -> mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) -> mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) -> plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) -> plus(x5,x4) 2.51/2.57 union(union(x4,x5),x6) -> union(x4,union(x5,x6)) 2.51/2.57 union(x4,x5) -> union(x5,x4) 2.51/2.57 MULT(mult(x4,x5),x6) -> MULT(x4,mult(x5,x6)) 2.51/2.57 MULT(x4,x5) -> MULT(x5,x4) 2.51/2.57 -> EAxioms: 2.51/2.57 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) = mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) = plus(x5,x4) 2.51/2.57 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.57 union(x4,x5) = union(x5,x4) 2.51/2.57 ->->-> Rules: 2.51/2.57 0(z) -> z 2.51/2.57 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.57 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.57 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.57 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.57 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.57 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.57 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.57 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.57 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.57 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.57 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.57 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.57 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.57 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.57 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.57 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.57 mult(z,X) -> z 2.51/2.57 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.57 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.57 prod(empty) -> 1(z) 2.51/2.57 prod(singl(X)) -> X 2.51/2.57 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.57 sum(empty) -> 0(z) 2.51/2.57 sum(singl(X)) -> X 2.51/2.57 union(empty,X) -> X 2.51/2.57 union(X,empty) -> X 2.51/2.57 -> SRules: 2.51/2.57 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.57 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.57 2.51/2.57 Problem 1.4: 2.51/2.57 2.51/2.57 Reduction Pairs Processor: 2.51/2.57 -> FAxioms: 2.51/2.57 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.57 MULT(x4,x5) = MULT(x5,x4) 2.51/2.57 -> Pairs: 2.51/2.57 MULT(mult(z,X),x4) -> MULT(z,x4) 2.51/2.57 -> EAxioms: 2.51/2.57 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) = mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) = plus(x5,x4) 2.51/2.57 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.57 union(x4,x5) = union(x5,x4) 2.51/2.57 -> Usable Equations: 2.51/2.57 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) = mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) = plus(x5,x4) 2.51/2.57 -> Rules: 2.51/2.57 0(z) -> z 2.51/2.57 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.57 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.57 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.57 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.57 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.57 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.57 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.57 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.57 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.57 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.57 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.57 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.57 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.57 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.57 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.57 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.57 mult(z,X) -> z 2.51/2.57 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.57 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.57 prod(empty) -> 1(z) 2.51/2.57 prod(singl(X)) -> X 2.51/2.57 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.57 sum(empty) -> 0(z) 2.51/2.57 sum(singl(X)) -> X 2.51/2.57 union(empty,X) -> X 2.51/2.57 union(X,empty) -> X 2.51/2.57 -> Usable Rules: 2.51/2.57 0(z) -> z 2.51/2.57 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.57 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.57 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.57 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.57 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.57 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.57 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.57 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.57 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.57 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.57 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.57 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.57 mult(z,X) -> z 2.51/2.57 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.57 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 -> SRules: 2.51/2.57 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.57 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.57 ->Interpretation type: 2.51/2.57 Linear 2.51/2.57 ->Coefficients: 2.51/2.57 Natural Numbers 2.51/2.57 ->Dimension: 2.51/2.57 1 2.51/2.57 ->Bound: 2.51/2.57 2 2.51/2.57 ->Interpretation: 2.51/2.57 2.51/2.57 [0](X) = 2 2.51/2.57 [U11](X1,X2,X3) = X1 + X3 + 2 2.51/2.57 [U12](X1,X2,X3) = 2.X1 + X3 2.51/2.57 [U21](X1,X2,X3) = X1 + X3 + 2 2.51/2.57 [U22](X1,X2,X3) = X1 + X3 + 2 2.51/2.57 [U31](X1,X2,X3) = X1 + 1 2.51/2.57 [U32](X1,X2,X3) = 2 2.51/2.57 [U41](X1,X2,X3) = X1 + 2 2.51/2.57 [U42](X1,X2,X3) = X1 + 1 2.51/2.57 [U51](X1,X2,X3) = X1 + 2 2.51/2.57 [U52](X1,X2,X3) = 2.X1 2.51/2.57 [U61](X1,X2,X3) = 0 2.51/2.57 [U62](X1,X2,X3) = 0 2.51/2.57 [U71](X1,X2,X3) = 0 2.51/2.57 [U72](X1,X2,X3) = 0 2.51/2.57 [mult](X1,X2) = X1 + X2 + 2 2.51/2.57 [plus](X1,X2) = X1 + X2 + 2 2.51/2.57 [prod](X) = 0 2.51/2.57 [sum](X) = 0 2.51/2.57 [union](X1,X2) = 0 2.51/2.57 [1](X) = 2 2.51/2.57 [empty] = 0 2.51/2.57 [singl](X) = 0 2.51/2.57 [tt] = 2 2.51/2.57 [z] = 0 2.51/2.57 [0#](X) = 0 2.51/2.57 [U11#](X1,X2,X3) = 0 2.51/2.57 [U12#](X1,X2,X3) = 0 2.51/2.57 [U21#](X1,X2,X3) = 0 2.51/2.57 [U22#](X1,X2,X3) = 0 2.51/2.57 [U31#](X1,X2,X3) = 0 2.51/2.57 [U32#](X1,X2,X3) = 0 2.51/2.57 [U41#](X1,X2,X3) = 0 2.51/2.57 [U42#](X1,X2,X3) = 0 2.51/2.57 [U51#](X1,X2,X3) = 0 2.51/2.57 [U52#](X1,X2,X3) = 0 2.51/2.57 [U61#](X1,X2,X3) = 0 2.51/2.57 [U62#](X1,X2,X3) = 0 2.51/2.57 [U71#](X1,X2,X3) = 0 2.51/2.57 [U72#](X1,X2,X3) = 0 2.51/2.57 [MULT](X1,X2) = 2.X1 + 2.X2 2.51/2.57 [PLUS](X1,X2) = 0 2.51/2.57 [PROD](X) = 0 2.51/2.57 [SUM](X) = 0 2.51/2.57 [UNION](X1,X2) = 0 2.51/2.57 2.51/2.57 Problem 1.4: 2.51/2.57 2.51/2.57 SCC Processor: 2.51/2.57 -> FAxioms: 2.51/2.57 MULT(mult(x4,x5),x6) = MULT(x4,mult(x5,x6)) 2.51/2.57 MULT(x4,x5) = MULT(x5,x4) 2.51/2.57 -> Pairs: 2.51/2.57 Empty 2.51/2.57 -> EAxioms: 2.51/2.57 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) = mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) = plus(x5,x4) 2.51/2.57 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.57 union(x4,x5) = union(x5,x4) 2.51/2.57 -> Rules: 2.51/2.57 0(z) -> z 2.51/2.57 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.57 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.57 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.57 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.57 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.57 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.57 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.57 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.57 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.57 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.57 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.57 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.57 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.57 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.57 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.57 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.57 mult(z,X) -> z 2.51/2.57 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.57 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.57 prod(empty) -> 1(z) 2.51/2.57 prod(singl(X)) -> X 2.51/2.57 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.57 sum(empty) -> 0(z) 2.51/2.57 sum(singl(X)) -> X 2.51/2.57 union(empty,X) -> X 2.51/2.57 union(X,empty) -> X 2.51/2.57 -> SRules: 2.51/2.57 MULT(mult(x4,x5),x6) -> MULT(x4,x5) 2.51/2.57 MULT(x4,mult(x5,x6)) -> MULT(x5,x6) 2.51/2.57 ->Strongly Connected Components: 2.51/2.57 There is no strongly connected component 2.51/2.57 2.51/2.57 The problem is finite. 2.51/2.57 2.51/2.57 Problem 1.5: 2.51/2.57 2.51/2.57 Reduction Pairs Processor: 2.51/2.57 -> FAxioms: 2.51/2.57 Empty 2.51/2.57 -> Pairs: 2.51/2.57 U61#(tt,A,B) -> U62#(tt,A,B) 2.51/2.57 U62#(tt,A,B) -> PROD(A) 2.51/2.57 U62#(tt,A,B) -> PROD(B) 2.51/2.57 PROD(union(A,B)) -> U61#(tt,A,B) 2.51/2.57 -> EAxioms: 2.51/2.57 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) = mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) = plus(x5,x4) 2.51/2.57 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.57 union(x4,x5) = union(x5,x4) 2.51/2.57 -> Usable Equations: 2.51/2.57 Empty 2.51/2.57 -> Rules: 2.51/2.57 0(z) -> z 2.51/2.57 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.57 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.57 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.57 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.57 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.57 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.57 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.57 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.57 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.57 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.57 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.57 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.57 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.57 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.57 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.57 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.57 mult(z,X) -> z 2.51/2.57 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.57 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.57 prod(empty) -> 1(z) 2.51/2.57 prod(singl(X)) -> X 2.51/2.57 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.57 sum(empty) -> 0(z) 2.51/2.57 sum(singl(X)) -> X 2.51/2.57 union(empty,X) -> X 2.51/2.57 union(X,empty) -> X 2.51/2.57 -> Usable Rules: 2.51/2.57 Empty 2.51/2.57 -> SRules: 2.51/2.57 Empty 2.51/2.57 ->Interpretation type: 2.51/2.57 Linear 2.51/2.57 ->Coefficients: 2.51/2.57 Natural Numbers 2.51/2.57 ->Dimension: 2.51/2.57 1 2.51/2.57 ->Bound: 2.51/2.57 2 2.51/2.57 ->Interpretation: 2.51/2.57 2.51/2.57 [0](X) = 0 2.51/2.57 [U11](X1,X2,X3) = 0 2.51/2.57 [U12](X1,X2,X3) = 0 2.51/2.57 [U21](X1,X2,X3) = 0 2.51/2.57 [U22](X1,X2,X3) = 0 2.51/2.57 [U31](X1,X2,X3) = 0 2.51/2.57 [U32](X1,X2,X3) = 0 2.51/2.57 [U41](X1,X2,X3) = 0 2.51/2.57 [U42](X1,X2,X3) = 0 2.51/2.57 [U51](X1,X2,X3) = 0 2.51/2.57 [U52](X1,X2,X3) = 0 2.51/2.57 [U61](X1,X2,X3) = 0 2.51/2.57 [U62](X1,X2,X3) = 0 2.51/2.57 [U71](X1,X2,X3) = 0 2.51/2.57 [U72](X1,X2,X3) = 0 2.51/2.57 [mult](X1,X2) = 0 2.51/2.57 [plus](X1,X2) = 0 2.51/2.57 [prod](X) = 0 2.51/2.57 [sum](X) = 0 2.51/2.57 [union](X1,X2) = 2.X1 + 2.X2 + 2 2.51/2.57 [1](X) = 0 2.51/2.57 [empty] = 0 2.51/2.57 [singl](X) = 0 2.51/2.57 [tt] = 0 2.51/2.57 [z] = 0 2.51/2.57 [0#](X) = 0 2.51/2.57 [U11#](X1,X2,X3) = 0 2.51/2.57 [U12#](X1,X2,X3) = 0 2.51/2.57 [U21#](X1,X2,X3) = 0 2.51/2.57 [U22#](X1,X2,X3) = 0 2.51/2.57 [U31#](X1,X2,X3) = 0 2.51/2.57 [U32#](X1,X2,X3) = 0 2.51/2.57 [U41#](X1,X2,X3) = 0 2.51/2.57 [U42#](X1,X2,X3) = 0 2.51/2.57 [U51#](X1,X2,X3) = 0 2.51/2.57 [U52#](X1,X2,X3) = 0 2.51/2.57 [U61#](X1,X2,X3) = 2.X1 + 2.X2 + 2.X3 + 2 2.51/2.57 [U62#](X1,X2,X3) = 2.X2 + 2.X3 2.51/2.57 [U71#](X1,X2,X3) = 0 2.51/2.57 [U72#](X1,X2,X3) = 0 2.51/2.57 [MULT](X1,X2) = 0 2.51/2.57 [PLUS](X1,X2) = 0 2.51/2.57 [PROD](X) = 2.X 2.51/2.57 [SUM](X) = 0 2.51/2.57 [UNION](X1,X2) = 0 2.51/2.57 2.51/2.57 Problem 1.5: 2.51/2.57 2.51/2.57 SCC Processor: 2.51/2.57 -> FAxioms: 2.51/2.57 Empty 2.51/2.57 -> Pairs: 2.51/2.57 U62#(tt,A,B) -> PROD(A) 2.51/2.57 U62#(tt,A,B) -> PROD(B) 2.51/2.57 PROD(union(A,B)) -> U61#(tt,A,B) 2.51/2.57 -> EAxioms: 2.51/2.57 mult(mult(x4,x5),x6) = mult(x4,mult(x5,x6)) 2.51/2.57 mult(x4,x5) = mult(x5,x4) 2.51/2.57 plus(plus(x4,x5),x6) = plus(x4,plus(x5,x6)) 2.51/2.57 plus(x4,x5) = plus(x5,x4) 2.51/2.57 union(union(x4,x5),x6) = union(x4,union(x5,x6)) 2.51/2.57 union(x4,x5) = union(x5,x4) 2.51/2.57 -> Rules: 2.51/2.57 0(z) -> z 2.51/2.57 U11(tt,X,Y) -> U12(tt,X,Y) 2.51/2.57 U12(tt,X,Y) -> 0(mult(X,Y)) 2.51/2.57 U21(tt,X,Y) -> U22(tt,X,Y) 2.51/2.57 U22(tt,X,Y) -> plus(0(mult(X,Y)),Y) 2.51/2.57 U31(tt,X,Y) -> U32(tt,X,Y) 2.51/2.57 U32(tt,X,Y) -> 0(plus(X,Y)) 2.51/2.57 U41(tt,X,Y) -> U42(tt,X,Y) 2.51/2.57 U42(tt,X,Y) -> 1(plus(X,Y)) 2.51/2.57 U51(tt,X,Y) -> U52(tt,X,Y) 2.51/2.57 U52(tt,X,Y) -> 0(plus(plus(X,Y),1(z))) 2.51/2.57 U61(tt,A,B) -> U62(tt,A,B) 2.51/2.57 U62(tt,A,B) -> mult(prod(A),prod(B)) 2.51/2.57 U71(tt,A,B) -> U72(tt,A,B) 2.51/2.57 U72(tt,A,B) -> plus(sum(A),sum(B)) 2.51/2.57 mult(0(X),Y) -> U11(tt,X,Y) 2.51/2.57 mult(1(X),Y) -> U21(tt,X,Y) 2.51/2.57 mult(z,X) -> z 2.51/2.57 plus(0(X),0(Y)) -> U31(tt,X,Y) 2.51/2.57 plus(0(X),1(Y)) -> U41(tt,X,Y) 2.51/2.57 plus(1(X),1(Y)) -> U51(tt,X,Y) 2.51/2.57 plus(z,X) -> X 2.51/2.57 prod(union(A,B)) -> U61(tt,A,B) 2.51/2.57 prod(empty) -> 1(z) 2.51/2.57 prod(singl(X)) -> X 2.51/2.57 sum(union(A,B)) -> U71(tt,A,B) 2.51/2.57 sum(empty) -> 0(z) 2.51/2.57 sum(singl(X)) -> X 2.51/2.57 union(empty,X) -> X 2.51/2.57 union(X,empty) -> X 2.51/2.57 -> SRules: 2.51/2.57 Empty 2.51/2.57 ->Strongly Connected Components: 2.51/2.57 There is no strongly connected component 2.51/2.57 2.51/2.57 The problem is finite. 2.51/2.57 EOF