15.68/5.69	YES
15.91/5.71	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
15.91/5.71	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
15.91/5.71	
15.91/5.71	
15.91/5.71	Termination of the given ETRS could be proven:
15.91/5.71	
15.91/5.71	(0) ETRS
15.91/5.71	(1) EquationalDependencyPairsProof [EQUIVALENT, 126 ms]
15.91/5.71	(2) EDP
15.91/5.71	(3) EDependencyGraphProof [EQUIVALENT, 0 ms]
15.91/5.71	(4) AND
15.91/5.71	    (5) EDP
15.91/5.71	        (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
15.91/5.71	        (7) EDP
15.91/5.71	        (8) EUsableRulesReductionPairsProof [EQUIVALENT, 28 ms]
15.91/5.71	        (9) EDP
15.91/5.71	        (10) EDependencyGraphProof [EQUIVALENT, 0 ms]
15.91/5.71	        (11) TRUE
15.91/5.71	    (12) EDP
15.91/5.71	        (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
15.91/5.71	        (14) EDP
15.91/5.71	        (15) EDPPoloProof [EQUIVALENT, 81 ms]
15.91/5.71	        (16) EDP
15.91/5.71	        (17) EDependencyGraphProof [EQUIVALENT, 0 ms]
15.91/5.71	        (18) EDP
15.91/5.71	        (19) EDPPoloProof [EQUIVALENT, 32 ms]
15.91/5.71	        (20) EDP
15.91/5.71	        (21) EDPPoloProof [EQUIVALENT, 45 ms]
15.91/5.71	        (22) EDP
15.91/5.71	        (23) EDependencyGraphProof [EQUIVALENT, 0 ms]
15.91/5.71	        (24) EDP
15.91/5.71	        (25) EDPPoloProof [EQUIVALENT, 0 ms]
15.91/5.71	        (26) EDP
15.91/5.71	        (27) PisEmptyProof [EQUIVALENT, 0 ms]
15.91/5.71	        (28) YES
15.91/5.71	    (29) EDP
15.91/5.71	        (30) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
15.91/5.71	        (31) EDP
15.91/5.71	        (32) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
15.91/5.71	        (33) EDP
15.91/5.71	        (34) PisEmptyProof [EQUIVALENT, 0 ms]
15.91/5.71	        (35) YES
15.91/5.71	    (36) EDP
15.91/5.71	        (37) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
15.91/5.71	        (38) EDP
15.91/5.71	        (39) EDPPoloProof [EQUIVALENT, 210 ms]
15.91/5.71	        (40) EDP
15.91/5.71	        (41) EDependencyGraphProof [EQUIVALENT, 0 ms]
15.91/5.71	        (42) EDP
15.91/5.71	        (43) EDPPoloProof [EQUIVALENT, 178 ms]
15.91/5.71	        (44) EDP
15.91/5.71	        (45) EDependencyGraphProof [EQUIVALENT, 0 ms]
15.91/5.71	        (46) EDP
15.91/5.71	        (47) EDPPoloProof [EQUIVALENT, 47 ms]
15.91/5.71	        (48) EDP
15.91/5.71	        (49) PisEmptyProof [EQUIVALENT, 0 ms]
15.91/5.71	        (50) YES
15.91/5.71	    (51) EDP
15.91/5.71	        (52) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
15.91/5.71	        (53) EDP
15.91/5.71	        (54) EUsableRulesReductionPairsProof [EQUIVALENT, 10 ms]
15.91/5.71	        (55) EDP
15.91/5.71	        (56) EDependencyGraphProof [EQUIVALENT, 0 ms]
15.91/5.71	        (57) TRUE
15.91/5.71	
15.91/5.71	
15.91/5.71	----------------------------------------
15.91/5.71	
15.91/5.71	(0)
15.91/5.71	Obligation:
15.91/5.71	Equational rewrite system:
15.91/5.71	The TRS R consists of the following rules:
15.91/5.71	
15.91/5.71	   union(X, empty) -> X
15.91/5.71	   union(empty, X) -> X
15.91/5.71	   0(z) -> z
15.91/5.71	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.71	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.71	   U11(tt) -> tt
15.91/5.71	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.71	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.71	   U121(tt, X) -> X
15.91/5.71	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.71	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.71	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.71	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.71	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.71	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.71	   U161(tt, X) -> X
15.91/5.71	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.71	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.71	   U181(tt, X) -> X
15.91/5.71	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.71	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.71	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.71	   U22(tt) -> tt
15.91/5.71	   U31(tt) -> tt
15.91/5.71	   U41(tt) -> tt
15.91/5.71	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.71	   U52(tt) -> tt
15.91/5.71	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(1) EquationalDependencyPairsProof (EQUIVALENT)
15.91/5.72	Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U101^1(tt, X, Y) -> U102^1(isBin(Y), X, Y)
15.91/5.72	   U101^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U102^1(tt, X, Y) -> 0^1(mult(X, Y))
15.91/5.72	   U102^1(tt, X, Y) -> MULT(X, Y)
15.91/5.72	   U111^1(tt, X, Y) -> U112^1(isBin(Y), X, Y)
15.91/5.72	   U111^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U112^1(tt, X, Y) -> PLUS(0(mult(X, Y)), Y)
15.91/5.72	   U112^1(tt, X, Y) -> 0^1(mult(X, Y))
15.91/5.72	   U112^1(tt, X, Y) -> MULT(X, Y)
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   U131^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U132^1(tt, X, Y) -> 0^1(plus(X, Y))
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   U141^1(tt, X, Y) -> U142^1(isBin(Y), X, Y)
15.91/5.72	   U141^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U142^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   U151^1(tt, X, Y) -> U152^1(isBin(Y), X, Y)
15.91/5.72	   U151^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U152^1(tt, X, Y) -> 0^1(plus(plus(X, Y), 1(z)))
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z))
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   U171^1(tt, A, B) -> U172^1(isBag(B), A, B)
15.91/5.72	   U171^1(tt, A, B) -> ISBAG(B)
15.91/5.72	   U172^1(tt, A, B) -> MULT(prod(A), prod(B))
15.91/5.72	   U172^1(tt, A, B) -> PROD(A)
15.91/5.72	   U172^1(tt, A, B) -> PROD(B)
15.91/5.72	   U191^1(tt, A, B) -> U192^1(isBag(B), A, B)
15.91/5.72	   U191^1(tt, A, B) -> ISBAG(B)
15.91/5.72	   U192^1(tt, A, B) -> PLUS(sum(A), sum(B))
15.91/5.72	   U192^1(tt, A, B) -> SUM(A)
15.91/5.72	   U192^1(tt, A, B) -> SUM(B)
15.91/5.72	   U21^1(tt, V2) -> U22^1(isBag(V2))
15.91/5.72	   U21^1(tt, V2) -> ISBAG(V2)
15.91/5.72	   U51^1(tt, V2) -> U52^1(isBin(V2))
15.91/5.72	   U51^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   U61^1(tt, V2) -> U62^1(isBin(V2))
15.91/5.72	   U61^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   ISBAG(singl(V1)) -> U11^1(isBin(V1))
15.91/5.72	   ISBAG(singl(V1)) -> ISBIN(V1)
15.91/5.72	   ISBAG(union(V1, V2)) -> U21^1(isBag(V1), V2)
15.91/5.72	   ISBAG(union(V1, V2)) -> ISBAG(V1)
15.91/5.72	   ISBIN(0(V1)) -> U31^1(isBin(V1))
15.91/5.72	   ISBIN(0(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(1(V1)) -> U41^1(isBin(V1))
15.91/5.72	   ISBIN(1(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(mult(V1, V2)) -> U51^1(isBin(V1), V2)
15.91/5.72	   ISBIN(mult(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(plus(V1, V2)) -> U61^1(isBin(V1), V2)
15.91/5.72	   ISBIN(plus(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(prod(V1)) -> U71^1(isBag(V1))
15.91/5.72	   ISBIN(prod(V1)) -> ISBAG(V1)
15.91/5.72	   ISBIN(sum(V1)) -> U81^1(isBag(V1))
15.91/5.72	   ISBIN(sum(V1)) -> ISBAG(V1)
15.91/5.72	   MULT(z, X) -> U91^1(isBin(X))
15.91/5.72	   MULT(z, X) -> ISBIN(X)
15.91/5.72	   MULT(0(X), Y) -> U101^1(isBin(X), X, Y)
15.91/5.72	   MULT(0(X), Y) -> ISBIN(X)
15.91/5.72	   MULT(1(X), Y) -> U111^1(isBin(X), X, Y)
15.91/5.72	   MULT(1(X), Y) -> ISBIN(X)
15.91/5.72	   PLUS(z, X) -> U121^1(isBin(X), X)
15.91/5.72	   PLUS(z, X) -> ISBIN(X)
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 0(Y)) -> ISBIN(X)
15.91/5.72	   PLUS(0(X), 1(Y)) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 1(Y)) -> ISBIN(X)
15.91/5.72	   PLUS(1(X), 1(Y)) -> U151^1(isBin(X), X, Y)
15.91/5.72	   PLUS(1(X), 1(Y)) -> ISBIN(X)
15.91/5.72	   PROD(singl(X)) -> U161^1(isBin(X), X)
15.91/5.72	   PROD(singl(X)) -> ISBIN(X)
15.91/5.72	   PROD(union(A, B)) -> U171^1(isBag(A), A, B)
15.91/5.72	   PROD(union(A, B)) -> ISBAG(A)
15.91/5.72	   SUM(empty) -> 0^1(z)
15.91/5.72	   SUM(singl(X)) -> U181^1(isBin(X), X)
15.91/5.72	   SUM(singl(X)) -> ISBIN(X)
15.91/5.72	   SUM(union(A, B)) -> U191^1(isBag(A), A, B)
15.91/5.72	   SUM(union(A, B)) -> ISBAG(A)
15.91/5.72	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.72	   MULT(mult(z, X), ext) -> U91^1(isBin(X))
15.91/5.72	   MULT(mult(z, X), ext) -> ISBIN(X)
15.91/5.72	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.72	   MULT(mult(0(X), Y), ext) -> U101^1(isBin(X), X, Y)
15.91/5.72	   MULT(mult(0(X), Y), ext) -> ISBIN(X)
15.91/5.72	   MULT(mult(1(X), Y), ext) -> MULT(U111(isBin(X), X, Y), ext)
15.91/5.72	   MULT(mult(1(X), Y), ext) -> U111^1(isBin(X), X, Y)
15.91/5.72	   MULT(mult(1(X), Y), ext) -> ISBIN(X)
15.91/5.72	   PLUS(plus(z, X), ext) -> PLUS(U121(isBin(X), X), ext)
15.91/5.72	   PLUS(plus(z, X), ext) -> U121^1(isBin(X), X)
15.91/5.72	   PLUS(plus(z, X), ext) -> ISBIN(X)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> ISBIN(X)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> ISBIN(X)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U151(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> U151^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> ISBIN(X)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   MULT(x, y) == MULT(y, x)
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	   UNION(x, y) == UNION(y, x)
15.91/5.72	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(2)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U101^1(tt, X, Y) -> U102^1(isBin(Y), X, Y)
15.91/5.72	   U101^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U102^1(tt, X, Y) -> 0^1(mult(X, Y))
15.91/5.72	   U102^1(tt, X, Y) -> MULT(X, Y)
15.91/5.72	   U111^1(tt, X, Y) -> U112^1(isBin(Y), X, Y)
15.91/5.72	   U111^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U112^1(tt, X, Y) -> PLUS(0(mult(X, Y)), Y)
15.91/5.72	   U112^1(tt, X, Y) -> 0^1(mult(X, Y))
15.91/5.72	   U112^1(tt, X, Y) -> MULT(X, Y)
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   U131^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U132^1(tt, X, Y) -> 0^1(plus(X, Y))
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   U141^1(tt, X, Y) -> U142^1(isBin(Y), X, Y)
15.91/5.72	   U141^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U142^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   U151^1(tt, X, Y) -> U152^1(isBin(Y), X, Y)
15.91/5.72	   U151^1(tt, X, Y) -> ISBIN(Y)
15.91/5.72	   U152^1(tt, X, Y) -> 0^1(plus(plus(X, Y), 1(z)))
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z))
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   U171^1(tt, A, B) -> U172^1(isBag(B), A, B)
15.91/5.72	   U171^1(tt, A, B) -> ISBAG(B)
15.91/5.72	   U172^1(tt, A, B) -> MULT(prod(A), prod(B))
15.91/5.72	   U172^1(tt, A, B) -> PROD(A)
15.91/5.72	   U172^1(tt, A, B) -> PROD(B)
15.91/5.72	   U191^1(tt, A, B) -> U192^1(isBag(B), A, B)
15.91/5.72	   U191^1(tt, A, B) -> ISBAG(B)
15.91/5.72	   U192^1(tt, A, B) -> PLUS(sum(A), sum(B))
15.91/5.72	   U192^1(tt, A, B) -> SUM(A)
15.91/5.72	   U192^1(tt, A, B) -> SUM(B)
15.91/5.72	   U21^1(tt, V2) -> U22^1(isBag(V2))
15.91/5.72	   U21^1(tt, V2) -> ISBAG(V2)
15.91/5.72	   U51^1(tt, V2) -> U52^1(isBin(V2))
15.91/5.72	   U51^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   U61^1(tt, V2) -> U62^1(isBin(V2))
15.91/5.72	   U61^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   ISBAG(singl(V1)) -> U11^1(isBin(V1))
15.91/5.72	   ISBAG(singl(V1)) -> ISBIN(V1)
15.91/5.72	   ISBAG(union(V1, V2)) -> U21^1(isBag(V1), V2)
15.91/5.72	   ISBAG(union(V1, V2)) -> ISBAG(V1)
15.91/5.72	   ISBIN(0(V1)) -> U31^1(isBin(V1))
15.91/5.72	   ISBIN(0(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(1(V1)) -> U41^1(isBin(V1))
15.91/5.72	   ISBIN(1(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(mult(V1, V2)) -> U51^1(isBin(V1), V2)
15.91/5.72	   ISBIN(mult(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(plus(V1, V2)) -> U61^1(isBin(V1), V2)
15.91/5.72	   ISBIN(plus(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(prod(V1)) -> U71^1(isBag(V1))
15.91/5.72	   ISBIN(prod(V1)) -> ISBAG(V1)
15.91/5.72	   ISBIN(sum(V1)) -> U81^1(isBag(V1))
15.91/5.72	   ISBIN(sum(V1)) -> ISBAG(V1)
15.91/5.72	   MULT(z, X) -> U91^1(isBin(X))
15.91/5.72	   MULT(z, X) -> ISBIN(X)
15.91/5.72	   MULT(0(X), Y) -> U101^1(isBin(X), X, Y)
15.91/5.72	   MULT(0(X), Y) -> ISBIN(X)
15.91/5.72	   MULT(1(X), Y) -> U111^1(isBin(X), X, Y)
15.91/5.72	   MULT(1(X), Y) -> ISBIN(X)
15.91/5.72	   PLUS(z, X) -> U121^1(isBin(X), X)
15.91/5.72	   PLUS(z, X) -> ISBIN(X)
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 0(Y)) -> ISBIN(X)
15.91/5.72	   PLUS(0(X), 1(Y)) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 1(Y)) -> ISBIN(X)
15.91/5.72	   PLUS(1(X), 1(Y)) -> U151^1(isBin(X), X, Y)
15.91/5.72	   PLUS(1(X), 1(Y)) -> ISBIN(X)
15.91/5.72	   PROD(singl(X)) -> U161^1(isBin(X), X)
15.91/5.72	   PROD(singl(X)) -> ISBIN(X)
15.91/5.72	   PROD(union(A, B)) -> U171^1(isBag(A), A, B)
15.91/5.72	   PROD(union(A, B)) -> ISBAG(A)
15.91/5.72	   SUM(empty) -> 0^1(z)
15.91/5.72	   SUM(singl(X)) -> U181^1(isBin(X), X)
15.91/5.72	   SUM(singl(X)) -> ISBIN(X)
15.91/5.72	   SUM(union(A, B)) -> U191^1(isBag(A), A, B)
15.91/5.72	   SUM(union(A, B)) -> ISBAG(A)
15.91/5.72	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.72	   MULT(mult(z, X), ext) -> U91^1(isBin(X))
15.91/5.72	   MULT(mult(z, X), ext) -> ISBIN(X)
15.91/5.72	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.72	   MULT(mult(0(X), Y), ext) -> U101^1(isBin(X), X, Y)
15.91/5.72	   MULT(mult(0(X), Y), ext) -> ISBIN(X)
15.91/5.72	   MULT(mult(1(X), Y), ext) -> MULT(U111(isBin(X), X, Y), ext)
15.91/5.72	   MULT(mult(1(X), Y), ext) -> U111^1(isBin(X), X, Y)
15.91/5.72	   MULT(mult(1(X), Y), ext) -> ISBIN(X)
15.91/5.72	   PLUS(plus(z, X), ext) -> PLUS(U121(isBin(X), X), ext)
15.91/5.72	   PLUS(plus(z, X), ext) -> U121^1(isBin(X), X)
15.91/5.72	   PLUS(plus(z, X), ext) -> ISBIN(X)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> ISBIN(X)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> ISBIN(X)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U151(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> U151^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> ISBIN(X)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   MULT(x, y) == MULT(y, x)
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	   UNION(x, y) == UNION(y, x)
15.91/5.72	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(3) EDependencyGraphProof (EQUIVALENT)
15.91/5.72	The approximation of the Equational Dependency Graph [DA_STEIN] contains 5 SCCs with 47 less nodes.
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(4)
15.91/5.72	Complex Obligation (AND)
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(5)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U51^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   ISBIN(plus(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(0(V1)) -> ISBIN(V1)
15.91/5.72	   U61^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   U21^1(tt, V2) -> ISBAG(V2)
15.91/5.72	   ISBAG(singl(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(prod(V1)) -> ISBAG(V1)
15.91/5.72	   ISBIN(1(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(sum(V1)) -> ISBAG(V1)
15.91/5.72	   ISBAG(union(V1, V2)) -> U21^1(isBag(V1), V2)
15.91/5.72	   ISBIN(plus(V1, V2)) -> U61^1(isBin(V1), V2)
15.91/5.72	   ISBIN(mult(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(mult(V1, V2)) -> U51^1(isBin(V1), V2)
15.91/5.72	   ISBAG(union(V1, V2)) -> ISBAG(V1)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   MULT(x, y) == MULT(y, x)
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	   UNION(x, y) == UNION(y, x)
15.91/5.72	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(6) ESharpUsableEquationsProof (EQUIVALENT)
15.91/5.72	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
15.91/5.72	   MULT(x, y) == MULT(y, x)
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	   UNION(x, y) == UNION(y, x)
15.91/5.72	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(7)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U51^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   ISBIN(plus(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(0(V1)) -> ISBIN(V1)
15.91/5.72	   U61^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   U21^1(tt, V2) -> ISBAG(V2)
15.91/5.72	   ISBAG(singl(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(prod(V1)) -> ISBAG(V1)
15.91/5.72	   ISBIN(1(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(sum(V1)) -> ISBAG(V1)
15.91/5.72	   ISBAG(union(V1, V2)) -> U21^1(isBag(V1), V2)
15.91/5.72	   ISBIN(plus(V1, V2)) -> U61^1(isBin(V1), V2)
15.91/5.72	   ISBIN(mult(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(mult(V1, V2)) -> U51^1(isBin(V1), V2)
15.91/5.72	   ISBAG(union(V1, V2)) -> ISBAG(V1)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	E# is empty.
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(8) EUsableRulesReductionPairsProof (EQUIVALENT)
15.91/5.72	By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
15.91/5.72	
15.91/5.72	The following dependency pairs can be deleted:
15.91/5.72	
15.91/5.72	   ISBIN(plus(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(0(V1)) -> ISBIN(V1)
15.91/5.72	   ISBAG(singl(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(prod(V1)) -> ISBAG(V1)
15.91/5.72	   ISBIN(1(V1)) -> ISBIN(V1)
15.91/5.72	   ISBIN(sum(V1)) -> ISBAG(V1)
15.91/5.72	   ISBAG(union(V1, V2)) -> U21^1(isBag(V1), V2)
15.91/5.72	   ISBIN(plus(V1, V2)) -> U61^1(isBin(V1), V2)
15.91/5.72	   ISBIN(mult(V1, V2)) -> ISBIN(V1)
15.91/5.72	   ISBIN(mult(V1, V2)) -> U51^1(isBin(V1), V2)
15.91/5.72	   ISBAG(union(V1, V2)) -> ISBAG(V1)
15.91/5.72	The following rules are removed from R:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	The following equations are removed from E:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.72	
15.91/5.72	   POL(0(x_1)) = 3 + 3*x_1
15.91/5.72	   POL(1(x_1)) = 3 + x_1
15.91/5.72	   POL(ISBAG(x_1)) = 3*x_1
15.91/5.72	   POL(ISBIN(x_1)) = 2*x_1
15.91/5.72	   POL(U11(x_1)) = 2*x_1
15.91/5.72	   POL(U21(x_1, x_2)) = x_1 + 3*x_2
15.91/5.72	   POL(U21^1(x_1, x_2)) = 2*x_1 + 3*x_2
15.91/5.72	   POL(U22(x_1)) = x_1
15.91/5.72	   POL(U31(x_1)) = 2*x_1
15.91/5.72	   POL(U41(x_1)) = x_1
15.91/5.72	   POL(U51(x_1, x_2)) = 2*x_1 + 3*x_2
15.91/5.72	   POL(U51^1(x_1, x_2)) = 2*x_1 + 3*x_2
15.91/5.72	   POL(U52(x_1)) = x_1
15.91/5.72	   POL(U61(x_1, x_2)) = 2*x_1 + 3*x_2
15.91/5.72	   POL(U61^1(x_1, x_2)) = 2*x_1 + 3*x_2
15.91/5.72	   POL(U62(x_1)) = x_1
15.91/5.72	   POL(U71(x_1)) = x_1
15.91/5.72	   POL(U81(x_1)) = x_1
15.91/5.72	   POL(empty) = 0
15.91/5.72	   POL(isBag(x_1)) = 2*x_1
15.91/5.72	   POL(isBin(x_1)) = 2*x_1
15.91/5.72	   POL(mult(x_1, x_2)) = 3*x_1 + 3*x_2
15.91/5.72	   POL(plus(x_1, x_2)) = 3 + 3*x_1 + 3*x_2
15.91/5.72	   POL(prod(x_1)) = 2*x_1
15.91/5.72	   POL(singl(x_1)) = 3*x_1
15.91/5.72	   POL(sum(x_1)) = 2*x_1
15.91/5.72	   POL(tt) = 0
15.91/5.72	   POL(union(x_1, x_2)) = 2*x_1 + 3*x_2
15.91/5.72	   POL(z) = 0
15.91/5.72	
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(9)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U51^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   U61^1(tt, V2) -> ISBIN(V2)
15.91/5.72	   U21^1(tt, V2) -> ISBAG(V2)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U62(tt) -> tt
15.91/5.72	
15.91/5.72	E is empty.
15.91/5.72	E# is empty.
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(10) EDependencyGraphProof (EQUIVALENT)
15.91/5.72	The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 3 less nodes.
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(11)
15.91/5.72	TRUE
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(12)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   U151^1(tt, X, Y) -> U152^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> U151^1(isBin(X), X, Y)
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z))
15.91/5.72	   U141^1(tt, X, Y) -> U142^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(1(X), 1(Y)) -> U151^1(isBin(X), X, Y)
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(z, X), ext) -> PLUS(U121(isBin(X), X), ext)
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   PLUS(0(X), 1(Y)) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U151(isBin(X), X, Y), ext)
15.91/5.72	   U142^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   MULT(x, y) == MULT(y, x)
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	   UNION(x, y) == UNION(y, x)
15.91/5.72	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(13) ESharpUsableEquationsProof (EQUIVALENT)
15.91/5.72	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
15.91/5.72	   MULT(x, y) == MULT(y, x)
15.91/5.72	   UNION(x, y) == UNION(y, x)
15.91/5.72	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.72	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(14)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   U151^1(tt, X, Y) -> U152^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> U151^1(isBin(X), X, Y)
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z))
15.91/5.72	   U141^1(tt, X, Y) -> U142^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(1(X), 1(Y)) -> U151^1(isBin(X), X, Y)
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(z, X), ext) -> PLUS(U121(isBin(X), X), ext)
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   PLUS(0(X), 1(Y)) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U151(isBin(X), X, Y), ext)
15.91/5.72	   U142^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(15) EDPPoloProof (EQUIVALENT)
15.91/5.72	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
15.91/5.72	
15.91/5.72	
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   U151^1(tt, X, Y) -> U152^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> U151^1(isBin(X), X, Y)
15.91/5.72	   U152^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z))
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(1(X), 1(Y)) -> U151^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 1(Y)) -> U141^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U151(isBin(X), X, Y), ext)
15.91/5.72	The remaining Dependency Pairs were at least non-strictly oriented.
15.91/5.72	
15.91/5.72	
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	   U141^1(tt, X, Y) -> U142^1(isBin(Y), X, Y)
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(z, X), ext) -> PLUS(U121(isBin(X), X), ext)
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	   U142^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
15.91/5.72	
15.91/5.72	
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   0(z) -> z
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U62(tt) -> tt
15.91/5.72	We had to orient the following equations of E# equivalently.
15.91/5.72	
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	With the implicit AFS we had to orient the following usable equations of E equivalently.
15.91/5.72	
15.91/5.72	
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.72	
15.91/5.72	   POL(0(x_1)) = x_1
15.91/5.72	   POL(1(x_1)) = 2 + x_1
15.91/5.72	   POL(PLUS(x_1, x_2)) = 2*x_1 + 2*x_2
15.91/5.72	   POL(U11(x_1)) = 2
15.91/5.72	   POL(U121(x_1, x_2)) = x_2
15.91/5.72	   POL(U131(x_1, x_2, x_3)) = x_2 + x_3
15.91/5.72	   POL(U131^1(x_1, x_2, x_3)) = 2*x_2 + 2*x_3
15.91/5.72	   POL(U132(x_1, x_2, x_3)) = x_2 + x_3
15.91/5.72	   POL(U132^1(x_1, x_2, x_3)) = 2*x_2 + 2*x_3
15.91/5.72	   POL(U141(x_1, x_2, x_3)) = 2 + x_2 + x_3
15.91/5.72	   POL(U141^1(x_1, x_2, x_3)) = 2*x_2 + 2*x_3
15.91/5.72	   POL(U142(x_1, x_2, x_3)) = 2 + x_2 + x_3
15.91/5.72	   POL(U142^1(x_1, x_2, x_3)) = 2*x_2 + 2*x_3
15.91/5.72	   POL(U151(x_1, x_2, x_3)) = 3 + x_2 + x_3
15.91/5.72	   POL(U151^1(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3
15.91/5.72	   POL(U152(x_1, x_2, x_3)) = x_1 + x_2 + x_3
15.91/5.72	   POL(U152^1(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3
15.91/5.72	   POL(U21(x_1, x_2)) = 2*x_1 + 2*x_2
15.91/5.72	   POL(U22(x_1)) = x_1
15.91/5.72	   POL(U31(x_1)) = x_1
15.91/5.72	   POL(U41(x_1)) = 2
15.91/5.72	   POL(U51(x_1, x_2)) = x_1
15.91/5.72	   POL(U52(x_1)) = 2
15.91/5.72	   POL(U61(x_1, x_2)) = 2
15.91/5.72	   POL(U62(x_1)) = x_1
15.91/5.72	   POL(U71(x_1)) = 2
15.91/5.72	   POL(U81(x_1)) = 2
15.91/5.72	   POL(empty) = 2
15.91/5.72	   POL(isBag(x_1)) = 2*x_1
15.91/5.72	   POL(isBin(x_1)) = 2
15.91/5.72	   POL(mult(x_1, x_2)) = 0
15.91/5.72	   POL(plus(x_1, x_2)) = x_1 + x_2
15.91/5.72	   POL(prod(x_1)) = 0
15.91/5.72	   POL(singl(x_1)) = 2
15.91/5.72	   POL(sum(x_1)) = 0
15.91/5.72	   POL(tt) = 2
15.91/5.72	   POL(union(x_1, x_2)) = 2 + 3*x_1 + 2*x_2
15.91/5.72	   POL(z) = 0
15.91/5.72	
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(16)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	   U141^1(tt, X, Y) -> U142^1(isBin(Y), X, Y)
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(z, X), ext) -> PLUS(U121(isBin(X), X), ext)
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	   U142^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(17) EDependencyGraphProof (EQUIVALENT)
15.91/5.72	The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 2 less nodes.
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(18)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(z, X), ext) -> PLUS(U121(isBin(X), X), ext)
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(19) EDPPoloProof (EQUIVALENT)
15.91/5.72	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
15.91/5.72	
15.91/5.72	
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> U131^1(isBin(X), X, Y)
15.91/5.72	   PLUS(plus(z, X), ext) -> PLUS(U121(isBin(X), X), ext)
15.91/5.72	The remaining Dependency Pairs were at least non-strictly oriented.
15.91/5.72	
15.91/5.72	
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
15.91/5.72	
15.91/5.72	
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   0(z) -> z
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	We had to orient the following equations of E# equivalently.
15.91/5.72	
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	With the implicit AFS we had to orient the following usable equations of E equivalently.
15.91/5.72	
15.91/5.72	
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.72	
15.91/5.72	   POL(0(x_1)) = x_1
15.91/5.72	   POL(1(x_1)) = 1 + x_1
15.91/5.72	   POL(PLUS(x_1, x_2)) = 3*x_1 + 3*x_2
15.91/5.72	   POL(U11(x_1)) = 3
15.91/5.72	   POL(U121(x_1, x_2)) = x_2
15.91/5.72	   POL(U131(x_1, x_2, x_3)) = 1 + x_2 + x_3
15.91/5.72	   POL(U131^1(x_1, x_2, x_3)) = 3*x_2 + 3*x_3
15.91/5.72	   POL(U132(x_1, x_2, x_3)) = 1 + x_2 + x_3
15.91/5.72	   POL(U132^1(x_1, x_2, x_3)) = 3*x_2 + 3*x_3
15.91/5.72	   POL(U141(x_1, x_2, x_3)) = 2 + x_2 + x_3
15.91/5.72	   POL(U142(x_1, x_2, x_3)) = 2 + x_2 + x_3
15.91/5.72	   POL(U151(x_1, x_2, x_3)) = 3 + x_2 + x_3
15.91/5.72	   POL(U152(x_1, x_2, x_3)) = 3 + x_2 + x_3
15.91/5.72	   POL(U21(x_1, x_2)) = 3 + 3*x_2
15.91/5.72	   POL(U22(x_1)) = 3
15.91/5.72	   POL(U31(x_1)) = 3
15.91/5.72	   POL(U41(x_1)) = 3
15.91/5.72	   POL(U51(x_1, x_2)) = 3 + 3*x_2
15.91/5.72	   POL(U52(x_1)) = 3
15.91/5.72	   POL(U61(x_1, x_2)) = 3 + 3*x_2
15.91/5.72	   POL(U62(x_1)) = 3
15.91/5.72	   POL(U71(x_1)) = 3
15.91/5.72	   POL(U81(x_1)) = 3
15.91/5.72	   POL(empty) = 0
15.91/5.72	   POL(isBag(x_1)) = 0
15.91/5.72	   POL(isBin(x_1)) = 0
15.91/5.72	   POL(mult(x_1, x_2)) = 0
15.91/5.72	   POL(plus(x_1, x_2)) = 1 + x_1 + x_2
15.91/5.72	   POL(prod(x_1)) = 0
15.91/5.72	   POL(singl(x_1)) = 0
15.91/5.72	   POL(sum(x_1)) = 0
15.91/5.72	   POL(tt) = 0
15.91/5.72	   POL(union(x_1, x_2)) = 0
15.91/5.72	   POL(z) = 0
15.91/5.72	
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(20)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(21) EDPPoloProof (EQUIVALENT)
15.91/5.72	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
15.91/5.72	
15.91/5.72	
15.91/5.72	   U131^1(tt, X, Y) -> U132^1(isBin(Y), X, Y)
15.91/5.72	   PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U141(isBin(X), X, Y), ext)
15.91/5.72	The remaining Dependency Pairs were at least non-strictly oriented.
15.91/5.72	
15.91/5.72	
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
15.91/5.72	
15.91/5.72	
15.91/5.72	   0(z) -> z
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	We had to orient the following equations of E# equivalently.
15.91/5.72	
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	With the implicit AFS we had to orient the following usable equations of E equivalently.
15.91/5.72	
15.91/5.72	
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.72	
15.91/5.72	   POL(0(x_1)) = 1 + x_1
15.91/5.72	   POL(1(x_1)) = 2 + x_1
15.91/5.72	   POL(PLUS(x_1, x_2)) = x_1 + x_2
15.91/5.72	   POL(U11(x_1)) = 3
15.91/5.72	   POL(U121(x_1, x_2)) = x_2
15.91/5.72	   POL(U131(x_1, x_2, x_3)) = 2 + x_2 + x_3
15.91/5.72	   POL(U131^1(x_1, x_2, x_3)) = 2 + x_2 + x_3
15.91/5.72	   POL(U132(x_1, x_2, x_3)) = 1 + x_2 + x_3
15.91/5.72	   POL(U132^1(x_1, x_2, x_3)) = x_2 + x_3
15.91/5.72	   POL(U141(x_1, x_2, x_3)) = 2 + x_2 + x_3
15.91/5.72	   POL(U142(x_1, x_2, x_3)) = 2 + x_2 + x_3
15.91/5.72	   POL(U151(x_1, x_2, x_3)) = 3 + x_2 + x_3
15.91/5.72	   POL(U152(x_1, x_2, x_3)) = 3 + x_2 + x_3
15.91/5.72	   POL(U21(x_1, x_2)) = 3 + 3*x_2
15.91/5.72	   POL(U22(x_1)) = 3
15.91/5.72	   POL(U31(x_1)) = 3
15.91/5.72	   POL(U41(x_1)) = 3
15.91/5.72	   POL(U51(x_1, x_2)) = 3 + 3*x_2
15.91/5.72	   POL(U52(x_1)) = 3
15.91/5.72	   POL(U61(x_1, x_2)) = 3 + 3*x_2
15.91/5.72	   POL(U62(x_1)) = 3
15.91/5.72	   POL(U71(x_1)) = 3
15.91/5.72	   POL(U81(x_1)) = 3
15.91/5.72	   POL(empty) = 0
15.91/5.72	   POL(isBag(x_1)) = 0
15.91/5.72	   POL(isBin(x_1)) = 0
15.91/5.72	   POL(mult(x_1, x_2)) = 0
15.91/5.72	   POL(plus(x_1, x_2)) = x_1 + x_2
15.91/5.72	   POL(prod(x_1)) = 0
15.91/5.72	   POL(singl(x_1)) = 0
15.91/5.72	   POL(sum(x_1)) = 0
15.91/5.72	   POL(tt) = 0
15.91/5.72	   POL(union(x_1, x_2)) = 0
15.91/5.72	   POL(z) = 0
15.91/5.72	
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(22)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   PLUS(0(X), 0(Y)) -> U131^1(isBin(X), X, Y)
15.91/5.72	   U132^1(tt, X, Y) -> PLUS(X, Y)
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(23) EDependencyGraphProof (EQUIVALENT)
15.91/5.72	The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 2 less nodes.
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(24)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(25) EDPPoloProof (EQUIVALENT)
15.91/5.72	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.
15.91/5.72	
15.91/5.72	
15.91/5.72	   PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U131(isBin(X), X, Y), ext)
15.91/5.72	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
15.91/5.72	
15.91/5.72	
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   0(z) -> z
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	We had to orient the following equations of E# equivalently.
15.91/5.72	
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	With the implicit AFS we had to orient the following usable equations of E equivalently.
15.91/5.72	
15.91/5.72	
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.72	
15.91/5.72	   POL(0(x_1)) = 0
15.91/5.72	   POL(1(x_1)) = 0
15.91/5.72	   POL(PLUS(x_1, x_2)) = 2*x_1 + 2*x_2
15.91/5.72	   POL(U11(x_1)) = 3
15.91/5.72	   POL(U121(x_1, x_2)) = x_2
15.91/5.72	   POL(U131(x_1, x_2, x_3)) = 0
15.91/5.72	   POL(U132(x_1, x_2, x_3)) = 0
15.91/5.72	   POL(U141(x_1, x_2, x_3)) = 0
15.91/5.72	   POL(U142(x_1, x_2, x_3)) = 0
15.91/5.72	   POL(U151(x_1, x_2, x_3)) = 1
15.91/5.72	   POL(U152(x_1, x_2, x_3)) = 0
15.91/5.72	   POL(U21(x_1, x_2)) = 3 + 3*x_2
15.91/5.72	   POL(U22(x_1)) = 3
15.91/5.72	   POL(U31(x_1)) = 3
15.91/5.72	   POL(U41(x_1)) = 3
15.91/5.72	   POL(U51(x_1, x_2)) = 3 + 3*x_2
15.91/5.72	   POL(U52(x_1)) = 3
15.91/5.72	   POL(U61(x_1, x_2)) = 3 + 3*x_2
15.91/5.72	   POL(U62(x_1)) = 3
15.91/5.72	   POL(U71(x_1)) = 3
15.91/5.72	   POL(U81(x_1)) = 3
15.91/5.72	   POL(empty) = 0
15.91/5.72	   POL(isBag(x_1)) = 0
15.91/5.72	   POL(isBin(x_1)) = 0
15.91/5.72	   POL(mult(x_1, x_2)) = 0
15.91/5.72	   POL(plus(x_1, x_2)) = 1 + x_1 + x_2
15.91/5.72	   POL(prod(x_1)) = 0
15.91/5.72	   POL(singl(x_1)) = 0
15.91/5.72	   POL(sum(x_1)) = 0
15.91/5.72	   POL(tt) = 0
15.91/5.72	   POL(union(x_1, x_2)) = 0
15.91/5.72	   POL(z) = 0
15.91/5.72	
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(26)
15.91/5.72	Obligation:
15.91/5.72	P is empty.
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(27) PisEmptyProof (EQUIVALENT)
15.91/5.72	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(28)
15.91/5.72	YES
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(29)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U192^1(tt, A, B) -> SUM(B)
15.91/5.72	   U191^1(tt, A, B) -> U192^1(isBag(B), A, B)
15.91/5.72	   SUM(union(A, B)) -> U191^1(isBag(A), A, B)
15.91/5.72	   U192^1(tt, A, B) -> SUM(A)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.72	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.72	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.72	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.72	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.72	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.72	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.72	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.72	
15.91/5.72	The set E consists of the following equations:
15.91/5.72	
15.91/5.72	   mult(x, y) == mult(y, x)
15.91/5.72	   plus(x, y) == plus(y, x)
15.91/5.72	   union(x, y) == union(y, x)
15.91/5.72	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.72	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.72	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.72	
15.91/5.72	The set E# consists of the following equations:
15.91/5.72	
15.91/5.72	   MULT(x, y) == MULT(y, x)
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	   UNION(x, y) == UNION(y, x)
15.91/5.72	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.72	
15.91/5.72	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(30) ESharpUsableEquationsProof (EQUIVALENT)
15.91/5.72	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
15.91/5.72	   MULT(x, y) == MULT(y, x)
15.91/5.72	   PLUS(x, y) == PLUS(y, x)
15.91/5.72	   UNION(x, y) == UNION(y, x)
15.91/5.72	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.72	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.72	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.72	
15.91/5.72	----------------------------------------
15.91/5.72	
15.91/5.72	(31)
15.91/5.72	Obligation:
15.91/5.72	The TRS P consists of the following rules:
15.91/5.72	
15.91/5.72	   U192^1(tt, A, B) -> SUM(B)
15.91/5.72	   U191^1(tt, A, B) -> U192^1(isBag(B), A, B)
15.91/5.72	   SUM(union(A, B)) -> U191^1(isBag(A), A, B)
15.91/5.72	   U192^1(tt, A, B) -> SUM(A)
15.91/5.72	
15.91/5.72	The TRS R consists of the following rules:
15.91/5.72	
15.91/5.72	   union(X, empty) -> X
15.91/5.72	   union(empty, X) -> X
15.91/5.72	   0(z) -> z
15.91/5.72	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.72	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.72	   U11(tt) -> tt
15.91/5.72	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.72	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.72	   U121(tt, X) -> X
15.91/5.72	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.72	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.72	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.72	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.72	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.72	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.72	   U161(tt, X) -> X
15.91/5.72	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.72	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.72	   U181(tt, X) -> X
15.91/5.72	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.72	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.72	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.72	   U22(tt) -> tt
15.91/5.72	   U31(tt) -> tt
15.91/5.72	   U41(tt) -> tt
15.91/5.72	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.72	   U52(tt) -> tt
15.91/5.72	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.72	   U62(tt) -> tt
15.91/5.72	   U71(tt) -> tt
15.91/5.72	   U81(tt) -> tt
15.91/5.72	   U91(tt) -> z
15.91/5.72	   isBag(empty) -> tt
15.91/5.72	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.72	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.72	   isBin(z) -> tt
15.91/5.72	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.72	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.72	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.72	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.72	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.72	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.72	   mult(z, X) -> U91(isBin(X))
15.91/5.72	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.72	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.72	   plus(z, X) -> U121(isBin(X), X)
15.91/5.72	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.72	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.72	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.72	   prod(empty) -> 1(z)
15.91/5.72	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.72	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.72	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	E# is empty.
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(32) EUsableRulesReductionPairsProof (EQUIVALENT)
15.91/5.73	By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
15.91/5.73	
15.91/5.73	The following dependency pairs can be deleted:
15.91/5.73	
15.91/5.73	   U192^1(tt, A, B) -> SUM(B)
15.91/5.73	   U191^1(tt, A, B) -> U192^1(isBag(B), A, B)
15.91/5.73	   SUM(union(A, B)) -> U191^1(isBag(A), A, B)
15.91/5.73	   U192^1(tt, A, B) -> SUM(A)
15.91/5.73	The following rules are removed from R:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	The following equations are removed from E:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.73	
15.91/5.73	   POL(0(x_1)) = 3 + 3*x_1
15.91/5.73	   POL(1(x_1)) = 1 + 2*x_1
15.91/5.73	   POL(SUM(x_1)) = x_1
15.91/5.73	   POL(U11(x_1)) = 2 + 2*x_1
15.91/5.73	   POL(U191^1(x_1, x_2, x_3)) = x_1 + x_2 + 3*x_3
15.91/5.73	   POL(U192^1(x_1, x_2, x_3)) = x_1 + x_2 + x_3
15.91/5.73	   POL(U21(x_1, x_2)) = 2*x_1 + 3*x_2
15.91/5.73	   POL(U22(x_1)) = x_1
15.91/5.73	   POL(U31(x_1)) = 2*x_1
15.91/5.73	   POL(U41(x_1)) = x_1
15.91/5.73	   POL(U51(x_1, x_2)) = x_1 + 3*x_2
15.91/5.73	   POL(U52(x_1)) = 2*x_1
15.91/5.73	   POL(U61(x_1, x_2)) = 1 + x_1 + 2*x_2
15.91/5.73	   POL(U62(x_1)) = 2*x_1
15.91/5.73	   POL(U71(x_1)) = 2 + x_1
15.91/5.73	   POL(U81(x_1)) = 2 + x_1
15.91/5.73	   POL(empty) = 2
15.91/5.73	   POL(isBag(x_1)) = 2*x_1
15.91/5.73	   POL(isBin(x_1)) = 1 + x_1
15.91/5.73	   POL(mult(x_1, x_2)) = 1 + 2*x_1 + 3*x_2
15.91/5.73	   POL(plus(x_1, x_2)) = 3 + 2*x_1 + 3*x_2
15.91/5.73	   POL(prod(x_1)) = 3 + 3*x_1
15.91/5.73	   POL(singl(x_1)) = 2 + 2*x_1
15.91/5.73	   POL(sum(x_1)) = 3 + 3*x_1
15.91/5.73	   POL(tt) = 2
15.91/5.73	   POL(union(x_1, x_2)) = 3*x_1 + 3*x_2
15.91/5.73	   POL(z) = 1
15.91/5.73	
15.91/5.73	
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(33)
15.91/5.73	Obligation:
15.91/5.73	P is empty.
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	
15.91/5.73	E is empty.
15.91/5.73	E# is empty.
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(34) PisEmptyProof (EQUIVALENT)
15.91/5.73	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(35)
15.91/5.73	YES
15.91/5.73	
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(36)
15.91/5.73	Obligation:
15.91/5.73	The TRS P consists of the following rules:
15.91/5.73	
15.91/5.73	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.73	   U112^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   MULT(mult(1(X), Y), ext) -> U111^1(isBin(X), X, Y)
15.91/5.73	   MULT(mult(1(X), Y), ext) -> MULT(U111(isBin(X), X, Y), ext)
15.91/5.73	   U102^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   U101^1(tt, X, Y) -> U102^1(isBin(Y), X, Y)
15.91/5.73	   MULT(1(X), Y) -> U111^1(isBin(X), X, Y)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> U101^1(isBin(X), X, Y)
15.91/5.73	   U111^1(tt, X, Y) -> U112^1(isBin(Y), X, Y)
15.91/5.73	   MULT(0(X), Y) -> U101^1(isBin(X), X, Y)
15.91/5.73	
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	The set E# consists of the following equations:
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   PLUS(x, y) == PLUS(y, x)
15.91/5.73	   UNION(x, y) == UNION(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.73	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.73	
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(37) ESharpUsableEquationsProof (EQUIVALENT)
15.91/5.73	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
15.91/5.73	   PLUS(x, y) == PLUS(y, x)
15.91/5.73	   UNION(x, y) == UNION(y, x)
15.91/5.73	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.73	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.73	
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(38)
15.91/5.73	Obligation:
15.91/5.73	The TRS P consists of the following rules:
15.91/5.73	
15.91/5.73	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.73	   U112^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   MULT(mult(1(X), Y), ext) -> U111^1(isBin(X), X, Y)
15.91/5.73	   MULT(mult(1(X), Y), ext) -> MULT(U111(isBin(X), X, Y), ext)
15.91/5.73	   U102^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   U101^1(tt, X, Y) -> U102^1(isBin(Y), X, Y)
15.91/5.73	   MULT(1(X), Y) -> U111^1(isBin(X), X, Y)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> U101^1(isBin(X), X, Y)
15.91/5.73	   U111^1(tt, X, Y) -> U112^1(isBin(Y), X, Y)
15.91/5.73	   MULT(0(X), Y) -> U101^1(isBin(X), X, Y)
15.91/5.73	
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	The set E# consists of the following equations:
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(39) EDPPoloProof (EQUIVALENT)
15.91/5.73	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
15.91/5.73	
15.91/5.73	
15.91/5.73	   MULT(mult(1(X), Y), ext) -> U111^1(isBin(X), X, Y)
15.91/5.73	   MULT(mult(1(X), Y), ext) -> MULT(U111(isBin(X), X, Y), ext)
15.91/5.73	   MULT(1(X), Y) -> U111^1(isBin(X), X, Y)
15.91/5.73	The remaining Dependency Pairs were at least non-strictly oriented.
15.91/5.73	
15.91/5.73	
15.91/5.73	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.73	   U112^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   U102^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   U101^1(tt, X, Y) -> U102^1(isBin(Y), X, Y)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> U101^1(isBin(X), X, Y)
15.91/5.73	   U111^1(tt, X, Y) -> U112^1(isBin(Y), X, Y)
15.91/5.73	   MULT(0(X), Y) -> U101^1(isBin(X), X, Y)
15.91/5.73	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
15.91/5.73	
15.91/5.73	
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   0(z) -> z
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	We had to orient the following equations of E# equivalently.
15.91/5.73	
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	With the implicit AFS we had to orient the following usable equations of E equivalently.
15.91/5.73	
15.91/5.73	
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.73	
15.91/5.73	   POL(0(x_1)) = x_1
15.91/5.73	   POL(1(x_1)) = 1 + x_1
15.91/5.73	   POL(MULT(x_1, x_2)) = x_1 + x_1*x_2 + x_2
15.91/5.73	   POL(U101(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3
15.91/5.73	   POL(U101^1(x_1, x_2, x_3)) = x_1*x_2*x_3 + x_2 + x_3
15.91/5.73	   POL(U102(x_1, x_2, x_3)) = x_1*x_2 + x_1*x_3 + x_2*x_3
15.91/5.73	   POL(U102^1(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3
15.91/5.73	   POL(U11(x_1)) = 1
15.91/5.73	   POL(U111(x_1, x_2, x_3)) = x_1*x_3 + x_2 + x_2*x_3 + x_3
15.91/5.73	   POL(U111^1(x_1, x_2, x_3)) = x_1*x_2*x_3 + x_1*x_3 + x_2
15.91/5.73	   POL(U112(x_1, x_2, x_3)) = x_1*x_3 + x_2 + x_2*x_3 + x_3
15.91/5.73	   POL(U112^1(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3
15.91/5.73	   POL(U121(x_1, x_2)) = x_1*x_2
15.91/5.73	   POL(U131(x_1, x_2, x_3)) = x_2 + x_3
15.91/5.73	   POL(U132(x_1, x_2, x_3)) = x_1*x_2 + x_1*x_3
15.91/5.73	   POL(U141(x_1, x_2, x_3)) = 1 + x_2 + x_3
15.91/5.73	   POL(U142(x_1, x_2, x_3)) = 1 + x_1*x_2 + x_1*x_3
15.91/5.73	   POL(U151(x_1, x_2, x_3)) = 1 + x_1*x_2 + x_1*x_3
15.91/5.73	   POL(U152(x_1, x_2, x_3)) = 1 + x_2 + x_3
15.91/5.73	   POL(U21(x_1, x_2)) = 1
15.91/5.73	   POL(U22(x_1)) = x_1^2
15.91/5.73	   POL(U31(x_1)) = 1
15.91/5.73	   POL(U41(x_1)) = x_1^2
15.91/5.73	   POL(U51(x_1, x_2)) = x_1
15.91/5.73	   POL(U52(x_1)) = 1
15.91/5.73	   POL(U61(x_1, x_2)) = x_1
15.91/5.73	   POL(U62(x_1)) = 1
15.91/5.73	   POL(U71(x_1)) = 1
15.91/5.73	   POL(U81(x_1)) = x_1^2
15.91/5.73	   POL(U91(x_1)) = 0
15.91/5.73	   POL(empty) = 1
15.91/5.73	   POL(isBag(x_1)) = 1
15.91/5.73	   POL(isBin(x_1)) = 1
15.91/5.73	   POL(mult(x_1, x_2)) = x_1 + x_1*x_2 + x_2
15.91/5.73	   POL(plus(x_1, x_2)) = x_1 + x_2
15.91/5.73	   POL(prod(x_1)) = 0
15.91/5.73	   POL(singl(x_1)) = 0
15.91/5.73	   POL(sum(x_1)) = 0
15.91/5.73	   POL(tt) = 1
15.91/5.73	   POL(union(x_1, x_2)) = 1 + x_1 + x_1*x_2 + x_2
15.91/5.73	   POL(z) = 0
15.91/5.73	
15.91/5.73	
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(40)
15.91/5.73	Obligation:
15.91/5.73	The TRS P consists of the following rules:
15.91/5.73	
15.91/5.73	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.73	   U112^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   U102^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   U101^1(tt, X, Y) -> U102^1(isBin(Y), X, Y)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> U101^1(isBin(X), X, Y)
15.91/5.73	   U111^1(tt, X, Y) -> U112^1(isBin(Y), X, Y)
15.91/5.73	   MULT(0(X), Y) -> U101^1(isBin(X), X, Y)
15.91/5.73	
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	The set E# consists of the following equations:
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(41) EDependencyGraphProof (EQUIVALENT)
15.91/5.73	The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 2 less nodes.
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(42)
15.91/5.73	Obligation:
15.91/5.73	The TRS P consists of the following rules:
15.91/5.73	
15.91/5.73	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.73	   U101^1(tt, X, Y) -> U102^1(isBin(Y), X, Y)
15.91/5.73	   U102^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> U101^1(isBin(X), X, Y)
15.91/5.73	   MULT(0(X), Y) -> U101^1(isBin(X), X, Y)
15.91/5.73	
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	The set E# consists of the following equations:
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(43) EDPPoloProof (EQUIVALENT)
15.91/5.73	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented.
15.91/5.73	
15.91/5.73	
15.91/5.73	   MULT(mult(0(X), Y), ext) -> U101^1(isBin(X), X, Y)
15.91/5.73	   MULT(0(X), Y) -> U101^1(isBin(X), X, Y)
15.91/5.73	The remaining Dependency Pairs were at least non-strictly oriented.
15.91/5.73	
15.91/5.73	
15.91/5.73	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.73	   U101^1(tt, X, Y) -> U102^1(isBin(Y), X, Y)
15.91/5.73	   U102^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.73	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
15.91/5.73	
15.91/5.73	
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   0(z) -> z
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   U91(tt) -> z
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	We had to orient the following equations of E# equivalently.
15.91/5.73	
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	With the implicit AFS we had to orient the following usable equations of E equivalently.
15.91/5.73	
15.91/5.73	
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.73	
15.91/5.73	   POL(0(x_1)) = 1 + x_1
15.91/5.73	   POL(1(x_1)) = 1 + x_1
15.91/5.73	   POL(MULT(x_1, x_2)) = x_1 + x_1*x_2 + x_2
15.91/5.73	   POL(U101(x_1, x_2, x_3)) = x_1 + x_1*x_2 + x_1*x_2*x_3 + x_1*x_3 + x_3
15.91/5.73	   POL(U101^1(x_1, x_2, x_3)) = x_1*x_2*x_3 + x_1*x_3 + x_2
15.91/5.73	   POL(U102(x_1, x_2, x_3)) = x_1 + x_2 + x_2*x_3 + x_3
15.91/5.73	   POL(U102^1(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3
15.91/5.73	   POL(U11(x_1)) = 1
15.91/5.73	   POL(U111(x_1, x_2, x_3)) = x_1 + x_1*x_2 + x_1*x_3 + x_2*x_3 + x_3
15.91/5.73	   POL(U112(x_1, x_2, x_3)) = 1 + x_1*x_2*x_3 + x_1*x_3 + x_2 + x_3
15.91/5.73	   POL(U121(x_1, x_2)) = x_1*x_2
15.91/5.73	   POL(U131(x_1, x_2, x_3)) = 1 + x_1*x_2 + x_1*x_3
15.91/5.73	   POL(U132(x_1, x_2, x_3)) = 1 + x_1*x_2 + x_3
15.91/5.73	   POL(U141(x_1, x_2, x_3)) = x_1 + x_2 + x_3
15.91/5.73	   POL(U142(x_1, x_2, x_3)) = 1 + x_2 + x_3
15.91/5.73	   POL(U151(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3
15.91/5.73	   POL(U152(x_1, x_2, x_3)) = 1 + x_1 + x_1*x_2 + x_3
15.91/5.73	   POL(U21(x_1, x_2)) = x_1*x_2
15.91/5.73	   POL(U22(x_1)) = x_1
15.91/5.73	   POL(U31(x_1)) = 1
15.91/5.73	   POL(U41(x_1)) = 1
15.91/5.73	   POL(U51(x_1, x_2)) = x_1
15.91/5.73	   POL(U52(x_1)) = 1
15.91/5.73	   POL(U61(x_1, x_2)) = x_1
15.91/5.73	   POL(U62(x_1)) = 1
15.91/5.73	   POL(U71(x_1)) = 1
15.91/5.73	   POL(U81(x_1)) = 1
15.91/5.73	   POL(U91(x_1)) = 0
15.91/5.73	   POL(empty) = 1
15.91/5.73	   POL(isBag(x_1)) = x_1
15.91/5.73	   POL(isBin(x_1)) = 1
15.91/5.73	   POL(mult(x_1, x_2)) = x_1 + x_1*x_2 + x_2
15.91/5.73	   POL(plus(x_1, x_2)) = x_1 + x_2
15.91/5.73	   POL(prod(x_1)) = 0
15.91/5.73	   POL(singl(x_1)) = 1
15.91/5.73	   POL(sum(x_1)) = 0
15.91/5.73	   POL(tt) = 1
15.91/5.73	   POL(union(x_1, x_2)) = x_1 + x_1*x_2 + x_2
15.91/5.73	   POL(z) = 0
15.91/5.73	
15.91/5.73	
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(44)
15.91/5.73	Obligation:
15.91/5.73	The TRS P consists of the following rules:
15.91/5.73	
15.91/5.73	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.73	   U101^1(tt, X, Y) -> U102^1(isBin(Y), X, Y)
15.91/5.73	   U102^1(tt, X, Y) -> MULT(X, Y)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	The set E# consists of the following equations:
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(45) EDependencyGraphProof (EQUIVALENT)
15.91/5.73	The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 2 less nodes.
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(46)
15.91/5.73	Obligation:
15.91/5.73	The TRS P consists of the following rules:
15.91/5.73	
15.91/5.73	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	The set E# consists of the following equations:
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(47) EDPPoloProof (EQUIVALENT)
15.91/5.73	We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented.
15.91/5.73	
15.91/5.73	
15.91/5.73	   MULT(mult(z, X), ext) -> MULT(U91(isBin(X)), ext)
15.91/5.73	   MULT(mult(0(X), Y), ext) -> MULT(U101(isBin(X), X, Y), ext)
15.91/5.73	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
15.91/5.73	
15.91/5.73	
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   0(z) -> z
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U91(tt) -> z
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	We had to orient the following equations of E# equivalently.
15.91/5.73	
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	With the implicit AFS we had to orient the following usable equations of E equivalently.
15.91/5.73	
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.73	
15.91/5.73	   POL(0(x_1)) = 0
15.91/5.73	   POL(1(x_1)) = 3
15.91/5.73	   POL(MULT(x_1, x_2)) = x_1 + x_2
15.91/5.73	   POL(U101(x_1, x_2, x_3)) = 0
15.91/5.73	   POL(U102(x_1, x_2, x_3)) = 0
15.91/5.73	   POL(U11(x_1)) = 3
15.91/5.73	   POL(U111(x_1, x_2, x_3)) = 2 + x_3
15.91/5.73	   POL(U112(x_1, x_2, x_3)) = 2 + x_3
15.91/5.73	   POL(U121(x_1, x_2)) = x_2
15.91/5.73	   POL(U131(x_1, x_2, x_3)) = 2
15.91/5.73	   POL(U132(x_1, x_2, x_3)) = 2
15.91/5.73	   POL(U141(x_1, x_2, x_3)) = 3
15.91/5.73	   POL(U142(x_1, x_2, x_3)) = 3
15.91/5.73	   POL(U151(x_1, x_2, x_3)) = 2
15.91/5.73	   POL(U152(x_1, x_2, x_3)) = 0
15.91/5.73	   POL(U21(x_1, x_2)) = 3 + 3*x_2
15.91/5.73	   POL(U22(x_1)) = 3
15.91/5.73	   POL(U31(x_1)) = 3
15.91/5.73	   POL(U41(x_1)) = 3
15.91/5.73	   POL(U51(x_1, x_2)) = 3 + 3*x_2
15.91/5.73	   POL(U52(x_1)) = 3
15.91/5.73	   POL(U61(x_1, x_2)) = 3 + 3*x_2
15.91/5.73	   POL(U62(x_1)) = 3
15.91/5.73	   POL(U71(x_1)) = 3
15.91/5.73	   POL(U81(x_1)) = 3
15.91/5.73	   POL(U91(x_1)) = 0
15.91/5.73	   POL(empty) = 0
15.91/5.73	   POL(isBag(x_1)) = 0
15.91/5.73	   POL(isBin(x_1)) = 0
15.91/5.73	   POL(mult(x_1, x_2)) = 2 + x_1 + x_2
15.91/5.73	   POL(plus(x_1, x_2)) = 2 + x_1 + x_2
15.91/5.73	   POL(prod(x_1)) = 0
15.91/5.73	   POL(singl(x_1)) = 0
15.91/5.73	   POL(sum(x_1)) = 0
15.91/5.73	   POL(tt) = 0
15.91/5.73	   POL(union(x_1, x_2)) = 0
15.91/5.73	   POL(z) = 0
15.91/5.73	
15.91/5.73	
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(48)
15.91/5.73	Obligation:
15.91/5.73	P is empty.
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	The set E# consists of the following equations:
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(49) PisEmptyProof (EQUIVALENT)
15.91/5.73	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(50)
15.91/5.73	YES
15.91/5.73	
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(51)
15.91/5.73	Obligation:
15.91/5.73	The TRS P consists of the following rules:
15.91/5.73	
15.91/5.73	   U171^1(tt, A, B) -> U172^1(isBag(B), A, B)
15.91/5.73	   U172^1(tt, A, B) -> PROD(B)
15.91/5.73	   U172^1(tt, A, B) -> PROD(A)
15.91/5.73	   PROD(union(A, B)) -> U171^1(isBag(A), A, B)
15.91/5.73	
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	The set E# consists of the following equations:
15.91/5.73	
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   PLUS(x, y) == PLUS(y, x)
15.91/5.73	   UNION(x, y) == UNION(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.73	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.73	
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(52) ESharpUsableEquationsProof (EQUIVALENT)
15.91/5.73	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
15.91/5.73	   MULT(x, y) == MULT(y, x)
15.91/5.73	   PLUS(x, y) == PLUS(y, x)
15.91/5.73	   UNION(x, y) == UNION(y, x)
15.91/5.73	   MULT(mult(x, y), z') == MULT(x, mult(y, z'))
15.91/5.73	   PLUS(plus(x, y), z') == PLUS(x, plus(y, z'))
15.91/5.73	   UNION(union(x, y), z') == UNION(x, union(y, z'))
15.91/5.73	
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(53)
15.91/5.73	Obligation:
15.91/5.73	The TRS P consists of the following rules:
15.91/5.73	
15.91/5.73	   U171^1(tt, A, B) -> U172^1(isBag(B), A, B)
15.91/5.73	   U172^1(tt, A, B) -> PROD(B)
15.91/5.73	   U172^1(tt, A, B) -> PROD(A)
15.91/5.73	   PROD(union(A, B)) -> U171^1(isBag(A), A, B)
15.91/5.73	
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U62(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	
15.91/5.73	The set E consists of the following equations:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	
15.91/5.73	E# is empty.
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(54) EUsableRulesReductionPairsProof (EQUIVALENT)
15.91/5.73	By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
15.91/5.73	
15.91/5.73	The following dependency pairs can be deleted:
15.91/5.73	
15.91/5.73	   PROD(union(A, B)) -> U171^1(isBag(A), A, B)
15.91/5.73	The following rules are removed from R:
15.91/5.73	
15.91/5.73	   union(X, empty) -> X
15.91/5.73	   union(empty, X) -> X
15.91/5.73	   0(z) -> z
15.91/5.73	   U101(tt, X, Y) -> U102(isBin(Y), X, Y)
15.91/5.73	   U102(tt, X, Y) -> 0(mult(X, Y))
15.91/5.73	   U111(tt, X, Y) -> U112(isBin(Y), X, Y)
15.91/5.73	   U112(tt, X, Y) -> plus(0(mult(X, Y)), Y)
15.91/5.73	   U121(tt, X) -> X
15.91/5.73	   U131(tt, X, Y) -> U132(isBin(Y), X, Y)
15.91/5.73	   U132(tt, X, Y) -> 0(plus(X, Y))
15.91/5.73	   U141(tt, X, Y) -> U142(isBin(Y), X, Y)
15.91/5.73	   U142(tt, X, Y) -> 1(plus(X, Y))
15.91/5.73	   U151(tt, X, Y) -> U152(isBin(Y), X, Y)
15.91/5.73	   U152(tt, X, Y) -> 0(plus(plus(X, Y), 1(z)))
15.91/5.73	   U161(tt, X) -> X
15.91/5.73	   U171(tt, A, B) -> U172(isBag(B), A, B)
15.91/5.73	   U172(tt, A, B) -> mult(prod(A), prod(B))
15.91/5.73	   U181(tt, X) -> X
15.91/5.73	   U191(tt, A, B) -> U192(isBag(B), A, B)
15.91/5.73	   U192(tt, A, B) -> plus(sum(A), sum(B))
15.91/5.73	   U51(tt, V2) -> U52(isBin(V2))
15.91/5.73	   U91(tt) -> z
15.91/5.73	   isBag(empty) -> tt
15.91/5.73	   isBag(singl(V1)) -> U11(isBin(V1))
15.91/5.73	   isBag(union(V1, V2)) -> U21(isBag(V1), V2)
15.91/5.73	   isBin(z) -> tt
15.91/5.73	   isBin(0(V1)) -> U31(isBin(V1))
15.91/5.73	   isBin(1(V1)) -> U41(isBin(V1))
15.91/5.73	   isBin(mult(V1, V2)) -> U51(isBin(V1), V2)
15.91/5.73	   isBin(plus(V1, V2)) -> U61(isBin(V1), V2)
15.91/5.73	   isBin(prod(V1)) -> U71(isBag(V1))
15.91/5.73	   isBin(sum(V1)) -> U81(isBag(V1))
15.91/5.73	   mult(z, X) -> U91(isBin(X))
15.91/5.73	   mult(0(X), Y) -> U101(isBin(X), X, Y)
15.91/5.73	   mult(1(X), Y) -> U111(isBin(X), X, Y)
15.91/5.73	   plus(z, X) -> U121(isBin(X), X)
15.91/5.73	   plus(0(X), 0(Y)) -> U131(isBin(X), X, Y)
15.91/5.73	   plus(0(X), 1(Y)) -> U141(isBin(X), X, Y)
15.91/5.73	   plus(1(X), 1(Y)) -> U151(isBin(X), X, Y)
15.91/5.73	   prod(empty) -> 1(z)
15.91/5.73	   prod(singl(X)) -> U161(isBin(X), X)
15.91/5.73	   prod(union(A, B)) -> U171(isBag(A), A, B)
15.91/5.73	   sum(empty) -> 0(z)
15.91/5.73	   sum(singl(X)) -> U181(isBin(X), X)
15.91/5.73	   sum(union(A, B)) -> U191(isBag(A), A, B)
15.91/5.73	   mult(mult(z, X), ext) -> mult(U91(isBin(X)), ext)
15.91/5.73	   mult(mult(0(X), Y), ext) -> mult(U101(isBin(X), X, Y), ext)
15.91/5.73	   mult(mult(1(X), Y), ext) -> mult(U111(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(z, X), ext) -> plus(U121(isBin(X), X), ext)
15.91/5.73	   plus(plus(0(X), 0(Y)), ext) -> plus(U131(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(0(X), 1(Y)), ext) -> plus(U141(isBin(X), X, Y), ext)
15.91/5.73	   plus(plus(1(X), 1(Y)), ext) -> plus(U151(isBin(X), X, Y), ext)
15.91/5.73	The following equations are removed from E:
15.91/5.73	
15.91/5.73	   mult(x, y) == mult(y, x)
15.91/5.73	   plus(x, y) == plus(y, x)
15.91/5.73	   union(x, y) == union(y, x)
15.91/5.73	   mult(mult(x, y), z') == mult(x, mult(y, z'))
15.91/5.73	   plus(plus(x, y), z') == plus(x, plus(y, z'))
15.91/5.73	   union(union(x, y), z') == union(x, union(y, z'))
15.91/5.73	Used ordering: POLO with Polynomial interpretation [POLO]:
15.91/5.73	
15.91/5.73	   POL(0(x_1)) = 2 + 3*x_1
15.91/5.73	   POL(1(x_1)) = 3*x_1
15.91/5.73	   POL(PROD(x_1)) = x_1
15.91/5.73	   POL(U11(x_1)) = 2*x_1
15.91/5.73	   POL(U171^1(x_1, x_2, x_3)) = x_1 + x_2 + 3*x_3
15.91/5.73	   POL(U172^1(x_1, x_2, x_3)) = x_1 + x_2 + x_3
15.91/5.73	   POL(U21(x_1, x_2)) = 2*x_1 + 3*x_2
15.91/5.73	   POL(U22(x_1)) = x_1
15.91/5.73	   POL(U31(x_1)) = 2*x_1
15.91/5.73	   POL(U41(x_1)) = 2*x_1
15.91/5.73	   POL(U51(x_1, x_2)) = 1 + 2*x_1 + 3*x_2
15.91/5.73	   POL(U52(x_1)) = x_1
15.91/5.73	   POL(U61(x_1, x_2)) = 2*x_1 + 3*x_2
15.91/5.73	   POL(U62(x_1)) = x_1
15.91/5.73	   POL(U71(x_1)) = x_1
15.91/5.73	   POL(U81(x_1)) = 2*x_1
15.91/5.73	   POL(empty) = 0
15.91/5.73	   POL(isBag(x_1)) = 2*x_1
15.91/5.73	   POL(isBin(x_1)) = 2*x_1
15.91/5.73	   POL(mult(x_1, x_2)) = 2 + 3*x_1 + 3*x_2
15.91/5.73	   POL(plus(x_1, x_2)) = 2 + 3*x_1 + 3*x_2
15.91/5.73	   POL(prod(x_1)) = 2*x_1
15.91/5.73	   POL(singl(x_1)) = 3*x_1
15.91/5.73	   POL(sum(x_1)) = 2*x_1
15.91/5.73	   POL(tt) = 0
15.91/5.73	   POL(union(x_1, x_2)) = 3*x_1 + 3*x_2
15.91/5.73	   POL(z) = 0
15.91/5.73	
15.91/5.73	
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(55)
15.91/5.73	Obligation:
15.91/5.73	The TRS P consists of the following rules:
15.91/5.73	
15.91/5.73	   U171^1(tt, A, B) -> U172^1(isBag(B), A, B)
15.91/5.73	   U172^1(tt, A, B) -> PROD(B)
15.91/5.73	   U172^1(tt, A, B) -> PROD(A)
15.91/5.73	
15.91/5.73	The TRS R consists of the following rules:
15.91/5.73	
15.91/5.73	   U22(tt) -> tt
15.91/5.73	   U81(tt) -> tt
15.91/5.73	   U41(tt) -> tt
15.91/5.73	   U61(tt, V2) -> U62(isBin(V2))
15.91/5.73	   U21(tt, V2) -> U22(isBag(V2))
15.91/5.73	   U11(tt) -> tt
15.91/5.73	   U52(tt) -> tt
15.91/5.73	   U71(tt) -> tt
15.91/5.73	   U31(tt) -> tt
15.91/5.73	   U62(tt) -> tt
15.91/5.73	
15.91/5.73	E is empty.
15.91/5.73	E# is empty.
15.91/5.73	We have to consider all minimal (P,E#,R,E)-chains
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(56) EDependencyGraphProof (EQUIVALENT)
15.91/5.73	The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 3 less nodes.
15.91/5.73	----------------------------------------
15.91/5.73	
15.91/5.73	(57)
15.91/5.73	TRUE
15.91/5.77	EOF