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