19.04/7.27 YES 19.29/7.30 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 19.29/7.30 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 19.29/7.30 19.29/7.30 19.29/7.30 Termination of the given ETRS could be proven: 19.29/7.30 19.29/7.30 (0) ETRS 19.29/7.30 (1) EquationalDependencyPairsProof [EQUIVALENT, 112 ms] 19.29/7.30 (2) EDP 19.29/7.30 (3) EDependencyGraphProof [EQUIVALENT, 0 ms] 19.29/7.30 (4) AND 19.29/7.30 (5) EDP 19.29/7.30 (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 19.29/7.30 (7) EDP 19.29/7.30 (8) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 19.29/7.30 (9) EDP 19.29/7.30 (10) PisEmptyProof [EQUIVALENT, 0 ms] 19.29/7.30 (11) YES 19.29/7.30 (12) EDP 19.29/7.30 (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 19.29/7.30 (14) EDP 19.29/7.30 (15) EDPPoloProof [EQUIVALENT, 151 ms] 19.29/7.30 (16) EDP 19.29/7.30 (17) EDependencyGraphProof [EQUIVALENT, 0 ms] 19.29/7.30 (18) EDP 19.29/7.30 (19) EDPPoloProof [EQUIVALENT, 18 ms] 19.29/7.30 (20) EDP 19.29/7.30 (21) PisEmptyProof [EQUIVALENT, 0 ms] 19.29/7.30 (22) YES 19.29/7.30 (23) EDP 19.29/7.30 (24) ESharpUsableEquationsProof [EQUIVALENT, 4 ms] 19.29/7.30 (25) EDP 19.29/7.30 (26) EDPPoloProof [EQUIVALENT, 781 ms] 19.29/7.30 (27) EDP 19.29/7.30 (28) EDependencyGraphProof [EQUIVALENT, 0 ms] 19.29/7.30 (29) EDP 19.29/7.30 (30) EDPPoloProof [EQUIVALENT, 765 ms] 19.29/7.30 (31) EDP 19.29/7.30 (32) EDPPoloProof [EQUIVALENT, 528 ms] 19.29/7.30 (33) EDP 19.29/7.30 (34) EDependencyGraphProof [EQUIVALENT, 0 ms] 19.29/7.30 (35) EDP 19.29/7.30 (36) EDPPoloProof [EQUIVALENT, 38 ms] 19.29/7.30 (37) EDP 19.29/7.30 (38) EDPPoloProof [EQUIVALENT, 34 ms] 19.29/7.30 (39) EDP 19.29/7.30 (40) PisEmptyProof [EQUIVALENT, 0 ms] 19.29/7.30 (41) YES 19.29/7.30 (42) EDP 19.29/7.30 (43) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 19.29/7.30 (44) EDP 19.29/7.30 (45) EUsableRulesReductionPairsProof [EQUIVALENT, 7 ms] 19.29/7.30 (46) EDP 19.29/7.30 (47) PisEmptyProof [EQUIVALENT, 0 ms] 19.29/7.30 (48) YES 19.29/7.30 (49) EDP 19.29/7.30 (50) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 19.29/7.30 (51) EDP 19.29/7.30 (52) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 19.29/7.30 (53) EDP 19.29/7.30 (54) EDependencyGraphProof [EQUIVALENT, 0 ms] 19.29/7.30 (55) TRUE 19.29/7.30 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (0) 19.29/7.30 Obligation: 19.29/7.30 Equational rewrite system: 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (1) EquationalDependencyPairsProof (EQUIVALENT) 19.29/7.30 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 U111^1(tt, A, B) -> PLUS(sum(A), sum(B)) 19.29/7.30 U111^1(tt, A, B) -> SUM(A) 19.29/7.30 U111^1(tt, A, B) -> SUM(B) 19.29/7.30 U21^1(tt, X, Y) -> 0^1(mult(X, Y)) 19.29/7.30 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 U31^1(tt, X, Y) -> PLUS(0(mult(X, Y)), Y) 19.29/7.30 U31^1(tt, X, Y) -> 0^1(mult(X, Y)) 19.29/7.30 U31^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 U51^1(tt, X, Y) -> 0^1(plus(X, Y)) 19.29/7.30 U51^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 U61^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 U71^1(tt, X, Y) -> 0^1(plus(plus(X, Y), 1(z))) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z)) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 U91^1(tt, A, B) -> MULT(prod(A), prod(B)) 19.29/7.30 U91^1(tt, A, B) -> PROD(A) 19.29/7.30 U91^1(tt, A, B) -> PROD(B) 19.29/7.30 ISBAG(singl(V1)) -> ISBIN(V1) 19.29/7.30 ISBAG(union(V1, V2)) -> AND(isBag(V1), isBag(V2)) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V1) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V2) 19.29/7.30 ISBIN(0(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(1(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(mult(V1, V2)) -> AND(isBin(V1), isBin(V2)) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBIN(plus(V1, V2)) -> AND(isBin(V1), isBin(V2)) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBIN(prod(V1)) -> ISBAG(V1) 19.29/7.30 ISBIN(sum(V1)) -> ISBAG(V1) 19.29/7.30 MULT(z, X) -> U11^1(isBin(X)) 19.29/7.30 MULT(z, X) -> ISBIN(X) 19.29/7.30 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(0(X), Y) -> AND(isBin(X), isBin(Y)) 19.29/7.30 MULT(0(X), Y) -> ISBIN(X) 19.29/7.30 MULT(0(X), Y) -> ISBIN(Y) 19.29/7.30 MULT(1(X), Y) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(1(X), Y) -> AND(isBin(X), isBin(Y)) 19.29/7.30 MULT(1(X), Y) -> ISBIN(X) 19.29/7.30 MULT(1(X), Y) -> ISBIN(Y) 19.29/7.30 PLUS(z, X) -> U41^1(isBin(X), X) 19.29/7.30 PLUS(z, X) -> ISBIN(X) 19.29/7.30 PLUS(0(X), 0(Y)) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(0(X), 0(Y)) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(0(X), 0(Y)) -> ISBIN(X) 19.29/7.30 PLUS(0(X), 0(Y)) -> ISBIN(Y) 19.29/7.30 PLUS(0(X), 1(Y)) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(0(X), 1(Y)) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(0(X), 1(Y)) -> ISBIN(X) 19.29/7.30 PLUS(0(X), 1(Y)) -> ISBIN(Y) 19.29/7.30 PLUS(1(X), 1(Y)) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(1(X), 1(Y)) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(1(X), 1(Y)) -> ISBIN(X) 19.29/7.30 PLUS(1(X), 1(Y)) -> ISBIN(Y) 19.29/7.30 PROD(singl(X)) -> U81^1(isBin(X), X) 19.29/7.30 PROD(singl(X)) -> ISBIN(X) 19.29/7.30 PROD(union(A, B)) -> U91^1(and(isBag(A), isBag(B)), A, B) 19.29/7.30 PROD(union(A, B)) -> AND(isBag(A), isBag(B)) 19.29/7.30 PROD(union(A, B)) -> ISBAG(A) 19.29/7.30 PROD(union(A, B)) -> ISBAG(B) 19.29/7.30 SUM(empty) -> 0^1(z) 19.29/7.30 SUM(singl(X)) -> U101^1(isBin(X), X) 19.29/7.30 SUM(singl(X)) -> ISBIN(X) 19.29/7.30 SUM(union(A, B)) -> U111^1(and(isBag(A), isBag(B)), A, B) 19.29/7.30 SUM(union(A, B)) -> AND(isBag(A), isBag(B)) 19.29/7.30 SUM(union(A, B)) -> ISBAG(A) 19.29/7.30 SUM(union(A, B)) -> ISBAG(B) 19.29/7.30 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.30 MULT(mult(z, X), ext) -> U11^1(isBin(X)) 19.29/7.30 MULT(mult(z, X), ext) -> ISBIN(X) 19.29/7.30 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(mult(0(X), Y), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 MULT(mult(0(X), Y), ext) -> ISBIN(X) 19.29/7.30 MULT(mult(0(X), Y), ext) -> ISBIN(Y) 19.29/7.30 MULT(mult(1(X), Y), ext) -> MULT(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(1(X), Y), ext) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(mult(1(X), Y), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 MULT(mult(1(X), Y), ext) -> ISBIN(X) 19.29/7.30 MULT(mult(1(X), Y), ext) -> ISBIN(Y) 19.29/7.30 PLUS(plus(z, X), ext) -> PLUS(U41(isBin(X), X), ext) 19.29/7.30 PLUS(plus(z, X), ext) -> U41^1(isBin(X), X) 19.29/7.30 PLUS(plus(z, X), ext) -> ISBIN(X) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> ISBIN(X) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> ISBIN(Y) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> ISBIN(X) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> ISBIN(Y) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> ISBIN(X) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> ISBIN(Y) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 MULT(x, y) == MULT(y, x) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 UNION(x, y) == UNION(y, x) 19.29/7.30 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (2) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 U111^1(tt, A, B) -> PLUS(sum(A), sum(B)) 19.29/7.30 U111^1(tt, A, B) -> SUM(A) 19.29/7.30 U111^1(tt, A, B) -> SUM(B) 19.29/7.30 U21^1(tt, X, Y) -> 0^1(mult(X, Y)) 19.29/7.30 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 U31^1(tt, X, Y) -> PLUS(0(mult(X, Y)), Y) 19.29/7.30 U31^1(tt, X, Y) -> 0^1(mult(X, Y)) 19.29/7.30 U31^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 U51^1(tt, X, Y) -> 0^1(plus(X, Y)) 19.29/7.30 U51^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 U61^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 U71^1(tt, X, Y) -> 0^1(plus(plus(X, Y), 1(z))) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z)) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 U91^1(tt, A, B) -> MULT(prod(A), prod(B)) 19.29/7.30 U91^1(tt, A, B) -> PROD(A) 19.29/7.30 U91^1(tt, A, B) -> PROD(B) 19.29/7.30 ISBAG(singl(V1)) -> ISBIN(V1) 19.29/7.30 ISBAG(union(V1, V2)) -> AND(isBag(V1), isBag(V2)) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V1) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V2) 19.29/7.30 ISBIN(0(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(1(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(mult(V1, V2)) -> AND(isBin(V1), isBin(V2)) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBIN(plus(V1, V2)) -> AND(isBin(V1), isBin(V2)) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBIN(prod(V1)) -> ISBAG(V1) 19.29/7.30 ISBIN(sum(V1)) -> ISBAG(V1) 19.29/7.30 MULT(z, X) -> U11^1(isBin(X)) 19.29/7.30 MULT(z, X) -> ISBIN(X) 19.29/7.30 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(0(X), Y) -> AND(isBin(X), isBin(Y)) 19.29/7.30 MULT(0(X), Y) -> ISBIN(X) 19.29/7.30 MULT(0(X), Y) -> ISBIN(Y) 19.29/7.30 MULT(1(X), Y) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(1(X), Y) -> AND(isBin(X), isBin(Y)) 19.29/7.30 MULT(1(X), Y) -> ISBIN(X) 19.29/7.30 MULT(1(X), Y) -> ISBIN(Y) 19.29/7.30 PLUS(z, X) -> U41^1(isBin(X), X) 19.29/7.30 PLUS(z, X) -> ISBIN(X) 19.29/7.30 PLUS(0(X), 0(Y)) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(0(X), 0(Y)) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(0(X), 0(Y)) -> ISBIN(X) 19.29/7.30 PLUS(0(X), 0(Y)) -> ISBIN(Y) 19.29/7.30 PLUS(0(X), 1(Y)) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(0(X), 1(Y)) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(0(X), 1(Y)) -> ISBIN(X) 19.29/7.30 PLUS(0(X), 1(Y)) -> ISBIN(Y) 19.29/7.30 PLUS(1(X), 1(Y)) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(1(X), 1(Y)) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(1(X), 1(Y)) -> ISBIN(X) 19.29/7.30 PLUS(1(X), 1(Y)) -> ISBIN(Y) 19.29/7.30 PROD(singl(X)) -> U81^1(isBin(X), X) 19.29/7.30 PROD(singl(X)) -> ISBIN(X) 19.29/7.30 PROD(union(A, B)) -> U91^1(and(isBag(A), isBag(B)), A, B) 19.29/7.30 PROD(union(A, B)) -> AND(isBag(A), isBag(B)) 19.29/7.30 PROD(union(A, B)) -> ISBAG(A) 19.29/7.30 PROD(union(A, B)) -> ISBAG(B) 19.29/7.30 SUM(empty) -> 0^1(z) 19.29/7.30 SUM(singl(X)) -> U101^1(isBin(X), X) 19.29/7.30 SUM(singl(X)) -> ISBIN(X) 19.29/7.30 SUM(union(A, B)) -> U111^1(and(isBag(A), isBag(B)), A, B) 19.29/7.30 SUM(union(A, B)) -> AND(isBag(A), isBag(B)) 19.29/7.30 SUM(union(A, B)) -> ISBAG(A) 19.29/7.30 SUM(union(A, B)) -> ISBAG(B) 19.29/7.30 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.30 MULT(mult(z, X), ext) -> U11^1(isBin(X)) 19.29/7.30 MULT(mult(z, X), ext) -> ISBIN(X) 19.29/7.30 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(mult(0(X), Y), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 MULT(mult(0(X), Y), ext) -> ISBIN(X) 19.29/7.30 MULT(mult(0(X), Y), ext) -> ISBIN(Y) 19.29/7.30 MULT(mult(1(X), Y), ext) -> MULT(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(1(X), Y), ext) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(mult(1(X), Y), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 MULT(mult(1(X), Y), ext) -> ISBIN(X) 19.29/7.30 MULT(mult(1(X), Y), ext) -> ISBIN(Y) 19.29/7.30 PLUS(plus(z, X), ext) -> PLUS(U41(isBin(X), X), ext) 19.29/7.30 PLUS(plus(z, X), ext) -> U41^1(isBin(X), X) 19.29/7.30 PLUS(plus(z, X), ext) -> ISBIN(X) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> ISBIN(X) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> ISBIN(Y) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> ISBIN(X) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> ISBIN(Y) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> AND(isBin(X), isBin(Y)) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> ISBIN(X) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> ISBIN(Y) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 MULT(x, y) == MULT(y, x) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 UNION(x, y) == UNION(y, x) 19.29/7.30 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (3) EDependencyGraphProof (EQUIVALENT) 19.29/7.30 The approximation of the Equational Dependency Graph [DA_STEIN] contains 5 SCCs with 59 less nodes. 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (4) 19.29/7.30 Complex Obligation (AND) 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (5) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 ISBIN(1(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(0(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(sum(V1)) -> ISBAG(V1) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V2) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBIN(prod(V1)) -> ISBAG(V1) 19.29/7.30 ISBAG(singl(V1)) -> ISBIN(V1) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V1) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 MULT(x, y) == MULT(y, x) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 UNION(x, y) == UNION(y, x) 19.29/7.30 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (6) ESharpUsableEquationsProof (EQUIVALENT) 19.29/7.30 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 19.29/7.30 MULT(x, y) == MULT(y, x) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 UNION(x, y) == UNION(y, x) 19.29/7.30 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (7) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 ISBIN(1(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(0(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(sum(V1)) -> ISBAG(V1) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V2) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBIN(prod(V1)) -> ISBAG(V1) 19.29/7.30 ISBAG(singl(V1)) -> ISBIN(V1) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V1) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 E# is empty. 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (8) EUsableRulesReductionPairsProof (EQUIVALENT) 19.29/7.30 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. 19.29/7.30 19.29/7.30 The following dependency pairs can be deleted: 19.29/7.30 19.29/7.30 ISBIN(1(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(0(V1)) -> ISBIN(V1) 19.29/7.30 ISBIN(sum(V1)) -> ISBAG(V1) 19.29/7.30 ISBIN(plus(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V2) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V1) 19.29/7.30 ISBIN(mult(V1, V2)) -> ISBIN(V2) 19.29/7.30 ISBIN(prod(V1)) -> ISBAG(V1) 19.29/7.30 ISBAG(singl(V1)) -> ISBIN(V1) 19.29/7.30 ISBAG(union(V1, V2)) -> ISBAG(V1) 19.29/7.30 The following rules are removed from R: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 The following equations are removed from E: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.30 19.29/7.30 POL(0(x_1)) = 3*x_1 19.29/7.30 POL(1(x_1)) = 3*x_1 19.29/7.30 POL(ISBAG(x_1)) = 2*x_1 19.29/7.30 POL(ISBIN(x_1)) = x_1 19.29/7.30 POL(mult(x_1, x_2)) = 3*x_1 + 3*x_2 19.29/7.30 POL(plus(x_1, x_2)) = 3*x_1 + 3*x_2 19.29/7.30 POL(prod(x_1)) = 3*x_1 19.29/7.30 POL(singl(x_1)) = 3*x_1 19.29/7.30 POL(sum(x_1)) = 3*x_1 19.29/7.30 POL(union(x_1, x_2)) = 3*x_1 + 3*x_2 19.29/7.30 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (9) 19.29/7.30 Obligation: 19.29/7.30 P is empty. 19.29/7.30 R is empty. 19.29/7.30 E is empty. 19.29/7.30 E# is empty. 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (10) PisEmptyProof (EQUIVALENT) 19.29/7.30 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (11) 19.29/7.30 YES 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (12) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 U61^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 PLUS(1(X), 1(Y)) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(z, X), ext) -> PLUS(U41(isBin(X), X), ext) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 PLUS(0(X), 1(Y)) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z)) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U51^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 PLUS(0(X), 0(Y)) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 MULT(x, y) == MULT(y, x) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 UNION(x, y) == UNION(y, x) 19.29/7.30 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (13) ESharpUsableEquationsProof (EQUIVALENT) 19.29/7.30 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 19.29/7.30 MULT(x, y) == MULT(y, x) 19.29/7.30 UNION(x, y) == UNION(y, x) 19.29/7.30 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.30 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (14) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 U61^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 PLUS(1(X), 1(Y)) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(z, X), ext) -> PLUS(U41(isBin(X), X), ext) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 PLUS(0(X), 1(Y)) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z)) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U51^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 PLUS(0(X), 0(Y)) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (15) EDPPoloProof (EQUIVALENT) 19.29/7.30 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. 19.29/7.30 19.29/7.30 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> PLUS(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 U61^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 PLUS(0(X), 1(Y)) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> PLUS(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 U71^1(tt, X, Y) -> PLUS(plus(X, Y), 1(z)) 19.29/7.30 PLUS(plus(0(X), 1(Y)), ext) -> U61^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U51^1(tt, X, Y) -> PLUS(X, Y) 19.29/7.30 PLUS(0(X), 0(Y)) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(0(X), 0(Y)), ext) -> U51^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 The remaining Dependency Pairs were at least non-strictly oriented. 19.29/7.30 19.29/7.30 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(1(X), 1(Y)) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(z, X), ext) -> PLUS(U41(isBin(X), X), ext) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 19.29/7.30 19.29/7.30 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 0(z) -> z 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 We had to orient the following equations of E# equivalently. 19.29/7.30 19.29/7.30 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 With the implicit AFS we had to orient the following usable equations of E equivalently. 19.29/7.30 19.29/7.30 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.30 19.29/7.30 POL(0(x_1)) = 1 + x_1 19.29/7.30 POL(1(x_1)) = 1 + x_1 19.29/7.30 POL(PLUS(x_1, x_2)) = x_1 + x_2 19.29/7.30 POL(U41(x_1, x_2)) = x_2 19.29/7.30 POL(U51(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.30 POL(U51^1(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.30 POL(U61(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.30 POL(U61^1(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.30 POL(U71(x_1, x_2, x_3)) = 2 + x_2 + x_3 19.29/7.30 POL(U71^1(x_1, x_2, x_3)) = 2 + x_2 + x_3 19.29/7.30 POL(and(x_1, x_2)) = 0 19.29/7.30 POL(empty) = 0 19.29/7.30 POL(isBag(x_1)) = 0 19.29/7.30 POL(isBin(x_1)) = 0 19.29/7.30 POL(mult(x_1, x_2)) = 0 19.29/7.30 POL(plus(x_1, x_2)) = x_1 + x_2 19.29/7.30 POL(prod(x_1)) = 3*x_1 19.29/7.30 POL(singl(x_1)) = 0 19.29/7.30 POL(sum(x_1)) = 0 19.29/7.30 POL(tt) = 0 19.29/7.30 POL(union(x_1, x_2)) = 0 19.29/7.30 POL(z) = 0 19.29/7.30 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (16) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(1(X), 1(Y)) -> U71^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 PLUS(plus(z, X), ext) -> PLUS(U41(isBin(X), X), ext) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (17) EDependencyGraphProof (EQUIVALENT) 19.29/7.30 The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 2 less nodes. 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (18) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 PLUS(plus(z, X), ext) -> PLUS(U41(isBin(X), X), ext) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (19) EDPPoloProof (EQUIVALENT) 19.29/7.30 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 19.29/7.30 19.29/7.30 19.29/7.30 PLUS(plus(z, X), ext) -> PLUS(U41(isBin(X), X), ext) 19.29/7.30 PLUS(plus(1(X), 1(Y)), ext) -> PLUS(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 19.29/7.30 19.29/7.30 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 We had to orient the following equations of E# equivalently. 19.29/7.30 19.29/7.30 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 With the implicit AFS we had to orient the following usable equations of E equivalently. 19.29/7.30 19.29/7.30 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.30 19.29/7.30 POL(0(x_1)) = 0 19.29/7.30 POL(1(x_1)) = 1 19.29/7.30 POL(PLUS(x_1, x_2)) = x_1 + x_2 19.29/7.30 POL(U41(x_1, x_2)) = 1 + x_2 19.29/7.30 POL(U51(x_1, x_2, x_3)) = 0 19.29/7.30 POL(U61(x_1, x_2, x_3)) = 1 19.29/7.30 POL(U71(x_1, x_2, x_3)) = 0 19.29/7.30 POL(and(x_1, x_2)) = 0 19.29/7.30 POL(empty) = 0 19.29/7.30 POL(isBag(x_1)) = 0 19.29/7.30 POL(isBin(x_1)) = 0 19.29/7.30 POL(mult(x_1, x_2)) = 0 19.29/7.30 POL(plus(x_1, x_2)) = 2 + x_1 + x_2 19.29/7.30 POL(prod(x_1)) = 0 19.29/7.30 POL(singl(x_1)) = 0 19.29/7.30 POL(sum(x_1)) = 3*x_1 19.29/7.30 POL(tt) = 0 19.29/7.30 POL(union(x_1, x_2)) = 0 19.29/7.30 POL(z) = 0 19.29/7.30 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (20) 19.29/7.30 Obligation: 19.29/7.30 P is empty. 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (21) PisEmptyProof (EQUIVALENT) 19.29/7.30 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (22) 19.29/7.30 YES 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (23) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 MULT(mult(1(X), Y), ext) -> MULT(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U31^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.30 MULT(mult(1(X), Y), ext) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 MULT(1(X), Y) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 MULT(x, y) == MULT(y, x) 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 UNION(x, y) == UNION(y, x) 19.29/7.30 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (24) ESharpUsableEquationsProof (EQUIVALENT) 19.29/7.30 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 19.29/7.30 PLUS(x, y) == PLUS(y, x) 19.29/7.30 UNION(x, y) == UNION(y, x) 19.29/7.30 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.30 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (25) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 MULT(mult(1(X), Y), ext) -> MULT(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U31^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.30 MULT(mult(1(X), Y), ext) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 MULT(1(X), Y) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 19.29/7.30 The set E consists of the following equations: 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 union(x, y) == union(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.30 19.29/7.30 The set E# consists of the following equations: 19.29/7.30 19.29/7.30 MULT(x, y) == MULT(y, x) 19.29/7.30 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.30 19.29/7.30 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (26) EDPPoloProof (EQUIVALENT) 19.29/7.30 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. 19.29/7.30 19.29/7.30 19.29/7.30 MULT(mult(1(X), Y), ext) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(1(X), Y) -> U31^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 The remaining Dependency Pairs were at least non-strictly oriented. 19.29/7.30 19.29/7.30 19.29/7.30 MULT(mult(1(X), Y), ext) -> MULT(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U31^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.30 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 19.29/7.30 19.29/7.30 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 and(tt, X) -> X 19.29/7.30 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 0(z) -> z 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 U11(tt) -> z 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.30 We had to orient the following equations of E# equivalently. 19.29/7.30 19.29/7.30 19.29/7.30 MULT(x, y) == MULT(y, x) 19.29/7.30 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.30 With the implicit AFS we had to orient the following usable equations of E equivalently. 19.29/7.30 19.29/7.30 19.29/7.30 mult(x, y) == mult(y, x) 19.29/7.30 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.30 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.30 plus(x, y) == plus(y, x) 19.29/7.30 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.30 19.29/7.30 POL(0(x_1)) = x_1 19.29/7.30 POL(1(x_1)) = 1 + x_1 19.29/7.30 POL(MULT(x_1, x_2)) = x_1 + x_1*x_2 + x_2 19.29/7.30 POL(U11(x_1)) = 0 19.29/7.30 POL(U21(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3 19.29/7.30 POL(U21^1(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3 19.29/7.30 POL(U31(x_1, x_2, x_3)) = x_1 + x_1*x_2 + x_1*x_2*x_3 + x_1*x_3 + x_3 19.29/7.30 POL(U31^1(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3 19.29/7.30 POL(U41(x_1, x_2)) = x_2 19.29/7.30 POL(U51(x_1, x_2, x_3)) = x_2 + x_3 19.29/7.30 POL(U61(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.30 POL(U71(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.30 POL(and(x_1, x_2)) = x_1*x_2 19.29/7.30 POL(empty) = 1 19.29/7.30 POL(isBag(x_1)) = 1 19.29/7.30 POL(isBin(x_1)) = 1 19.29/7.30 POL(mult(x_1, x_2)) = x_1 + x_1*x_2 + x_2 19.29/7.30 POL(plus(x_1, x_2)) = x_1 + x_2 19.29/7.30 POL(prod(x_1)) = 1 + x_1 + x_1^2 19.29/7.30 POL(singl(x_1)) = 1 + x_1 + x_1^2 19.29/7.30 POL(sum(x_1)) = 1 + x_1 + x_1^2 19.29/7.30 POL(tt) = 1 19.29/7.30 POL(union(x_1, x_2)) = x_1 + x_1*x_2 + x_2 19.29/7.30 POL(z) = 0 19.29/7.30 19.29/7.30 19.29/7.30 ---------------------------------------- 19.29/7.30 19.29/7.30 (27) 19.29/7.30 Obligation: 19.29/7.30 The TRS P consists of the following rules: 19.29/7.30 19.29/7.30 MULT(mult(1(X), Y), ext) -> MULT(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.30 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 U31^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.30 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.30 19.29/7.30 The TRS R consists of the following rules: 19.29/7.30 19.29/7.30 union(X, empty) -> X 19.29/7.30 union(empty, X) -> X 19.29/7.30 0(z) -> z 19.29/7.30 U101(tt, X) -> X 19.29/7.30 U11(tt) -> z 19.29/7.30 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.30 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.30 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.30 U41(tt, X) -> X 19.29/7.30 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.30 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.30 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.30 U81(tt, X) -> X 19.29/7.30 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.30 and(tt, X) -> X 19.29/7.30 isBag(empty) -> tt 19.29/7.30 isBag(singl(V1)) -> isBin(V1) 19.29/7.30 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.30 isBin(z) -> tt 19.29/7.30 isBin(0(V1)) -> isBin(V1) 19.29/7.30 isBin(1(V1)) -> isBin(V1) 19.29/7.30 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.30 isBin(prod(V1)) -> isBag(V1) 19.29/7.30 isBin(sum(V1)) -> isBag(V1) 19.29/7.30 mult(z, X) -> U11(isBin(X)) 19.29/7.30 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(z, X) -> U41(isBin(X), X) 19.29/7.30 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.30 prod(empty) -> 1(z) 19.29/7.30 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.30 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.30 sum(empty) -> 0(z) 19.29/7.30 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.30 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 The set E# consists of the following equations: 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (28) EDependencyGraphProof (EQUIVALENT) 19.29/7.31 The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 1 less node. 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (29) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 MULT(mult(1(X), Y), ext) -> MULT(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.31 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 The set E# consists of the following equations: 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (30) EDPPoloProof (EQUIVALENT) 19.29/7.31 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. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(mult(1(X), Y), ext) -> MULT(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 The remaining Dependency Pairs were at least non-strictly oriented. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.31 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.31 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 19.29/7.31 19.29/7.31 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 U11(tt) -> z 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 and(tt, X) -> X 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 0(z) -> z 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 We had to orient the following equations of E# equivalently. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 With the implicit AFS we had to orient the following usable equations of E equivalently. 19.29/7.31 19.29/7.31 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.31 19.29/7.31 POL(0(x_1)) = x_1 19.29/7.31 POL(1(x_1)) = 1 + x_1 19.29/7.31 POL(MULT(x_1, x_2)) = x_1 + x_1*x_2 + x_2 19.29/7.31 POL(U11(x_1)) = 0 19.29/7.31 POL(U21(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3 19.29/7.31 POL(U21^1(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3 19.29/7.31 POL(U31(x_1, x_2, x_3)) = x_1*x_3 + x_2 + x_2*x_3 + x_3 19.29/7.31 POL(U41(x_1, x_2)) = x_2 19.29/7.31 POL(U51(x_1, x_2, x_3)) = x_2 + x_3 19.29/7.31 POL(U61(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.31 POL(U71(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.31 POL(and(x_1, x_2)) = x_1*x_2 19.29/7.31 POL(empty) = 1 19.29/7.31 POL(isBag(x_1)) = 1 19.29/7.31 POL(isBin(x_1)) = 1 19.29/7.31 POL(mult(x_1, x_2)) = x_1 + x_1*x_2 + x_2 19.29/7.31 POL(plus(x_1, x_2)) = x_1 + x_2 19.29/7.31 POL(prod(x_1)) = 1 + x_1 + x_1^2 19.29/7.31 POL(singl(x_1)) = 1 + x_1 + x_1^2 19.29/7.31 POL(sum(x_1)) = 1 + x_1 + x_1^2 19.29/7.31 POL(tt) = 1 19.29/7.31 POL(union(x_1, x_2)) = x_1 + x_1*x_2 + x_2 19.29/7.31 POL(z) = 0 19.29/7.31 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (31) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.31 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 The set E# consists of the following equations: 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (32) EDPPoloProof (EQUIVALENT) 19.29/7.31 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. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(mult(0(X), Y), ext) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 MULT(0(X), Y) -> U21^1(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 The remaining Dependency Pairs were at least non-strictly oriented. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.31 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.31 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 19.29/7.31 19.29/7.31 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 U11(tt) -> z 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 0(z) -> z 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 We had to orient the following equations of E# equivalently. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 With the implicit AFS we had to orient the following usable equations of E equivalently. 19.29/7.31 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.31 19.29/7.31 POL(0(x_1)) = 1 + x_1 19.29/7.31 POL(1(x_1)) = 1 + x_1 19.29/7.31 POL(MULT(x_1, x_2)) = x_1 + x_1*x_2 + x_2 19.29/7.31 POL(U11(x_1)) = 0 19.29/7.31 POL(U21(x_1, x_2, x_3)) = 1 + x_1*x_2 + x_1*x_2*x_3 + x_1*x_3 19.29/7.31 POL(U21^1(x_1, x_2, x_3)) = x_2 + x_2*x_3 + x_3 19.29/7.31 POL(U31(x_1, x_2, x_3)) = 1 + x_1*x_2 + x_1*x_2*x_3 + x_1*x_3 + x_3 19.29/7.31 POL(U41(x_1, x_2)) = x_2 19.29/7.31 POL(U51(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.31 POL(U61(x_1, x_2, x_3)) = 1 + x_2 + x_3 19.29/7.31 POL(U71(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 19.29/7.31 POL(and(x_1, x_2)) = x_1*x_2 19.29/7.31 POL(empty) = 1 19.29/7.31 POL(isBag(x_1)) = 1 19.29/7.31 POL(isBin(x_1)) = 1 19.29/7.31 POL(mult(x_1, x_2)) = x_1 + x_1*x_2 + x_2 19.29/7.31 POL(plus(x_1, x_2)) = x_1 + x_2 19.29/7.31 POL(prod(x_1)) = 1 + x_1 + x_1^2 19.29/7.31 POL(singl(x_1)) = 1 + x_1 + x_1^2 19.29/7.31 POL(sum(x_1)) = 1 + x_1 + x_1^2 19.29/7.31 POL(tt) = 1 19.29/7.31 POL(union(x_1, x_2)) = x_1 + x_1*x_2 + x_2 19.29/7.31 POL(z) = 0 19.29/7.31 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (33) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.31 U21^1(tt, X, Y) -> MULT(X, Y) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 The set E# consists of the following equations: 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (34) EDependencyGraphProof (EQUIVALENT) 19.29/7.31 The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 1 less node. 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (35) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 The set E# consists of the following equations: 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (36) EDPPoloProof (EQUIVALENT) 19.29/7.31 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. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(mult(z, X), ext) -> MULT(U11(isBin(X)), ext) 19.29/7.31 The remaining Dependency Pairs were at least non-strictly oriented. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 19.29/7.31 19.29/7.31 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 0(z) -> z 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U11(tt) -> z 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 We had to orient the following equations of E# equivalently. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 With the implicit AFS we had to orient the following usable equations of E equivalently. 19.29/7.31 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.31 19.29/7.31 POL(0(x_1)) = 0 19.29/7.31 POL(1(x_1)) = 0 19.29/7.31 POL(MULT(x_1, x_2)) = x_1 + x_2 19.29/7.31 POL(U11(x_1)) = 0 19.29/7.31 POL(U21(x_1, x_2, x_3)) = 3 19.29/7.31 POL(U31(x_1, x_2, x_3)) = 2 + x_3 19.29/7.31 POL(U41(x_1, x_2)) = x_2 19.29/7.31 POL(U51(x_1, x_2, x_3)) = 2 19.29/7.31 POL(U61(x_1, x_2, x_3)) = 2 19.29/7.31 POL(U71(x_1, x_2, x_3)) = 2 19.29/7.31 POL(and(x_1, x_2)) = 0 19.29/7.31 POL(empty) = 0 19.29/7.31 POL(isBag(x_1)) = 0 19.29/7.31 POL(isBin(x_1)) = 0 19.29/7.31 POL(mult(x_1, x_2)) = 3 + x_1 + x_2 19.29/7.31 POL(plus(x_1, x_2)) = 2 + x_1 + x_2 19.29/7.31 POL(prod(x_1)) = 3*x_1 19.29/7.31 POL(singl(x_1)) = 0 19.29/7.31 POL(sum(x_1)) = 0 19.29/7.31 POL(tt) = 0 19.29/7.31 POL(union(x_1, x_2)) = 0 19.29/7.31 POL(z) = 0 19.29/7.31 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (37) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 The set E# consists of the following equations: 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (38) EDPPoloProof (EQUIVALENT) 19.29/7.31 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(mult(0(X), Y), ext) -> MULT(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 19.29/7.31 19.29/7.31 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U11(tt) -> z 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 We had to orient the following equations of E# equivalently. 19.29/7.31 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 With the implicit AFS we had to orient the following usable equations of E equivalently. 19.29/7.31 19.29/7.31 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.31 19.29/7.31 POL(0(x_1)) = 0 19.29/7.31 POL(1(x_1)) = 0 19.29/7.31 POL(MULT(x_1, x_2)) = x_1 + x_2 19.29/7.31 POL(U11(x_1)) = 0 19.29/7.31 POL(U21(x_1, x_2, x_3)) = 0 19.29/7.31 POL(U31(x_1, x_2, x_3)) = 1 + x_3 19.29/7.31 POL(U41(x_1, x_2)) = x_2 19.29/7.31 POL(U51(x_1, x_2, x_3)) = 0 19.29/7.31 POL(U61(x_1, x_2, x_3)) = 0 19.29/7.31 POL(U71(x_1, x_2, x_3)) = 0 19.29/7.31 POL(and(x_1, x_2)) = 0 19.29/7.31 POL(empty) = 0 19.29/7.31 POL(isBag(x_1)) = 0 19.29/7.31 POL(isBin(x_1)) = 0 19.29/7.31 POL(mult(x_1, x_2)) = 1 + x_1 + x_2 19.29/7.31 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 19.29/7.31 POL(prod(x_1)) = 0 19.29/7.31 POL(singl(x_1)) = 0 19.29/7.31 POL(sum(x_1)) = 3*x_1 19.29/7.31 POL(tt) = 0 19.29/7.31 POL(union(x_1, x_2)) = 0 19.29/7.31 POL(z) = 0 19.29/7.31 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (39) 19.29/7.31 Obligation: 19.29/7.31 P is empty. 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 The set E# consists of the following equations: 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (40) PisEmptyProof (EQUIVALENT) 19.29/7.31 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (41) 19.29/7.31 YES 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (42) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 U91^1(tt, A, B) -> PROD(A) 19.29/7.31 PROD(union(A, B)) -> U91^1(and(isBag(A), isBag(B)), A, B) 19.29/7.31 U91^1(tt, A, B) -> PROD(B) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 The set E# consists of the following equations: 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 PLUS(x, y) == PLUS(y, x) 19.29/7.31 UNION(x, y) == UNION(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.31 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.31 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (43) ESharpUsableEquationsProof (EQUIVALENT) 19.29/7.31 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 PLUS(x, y) == PLUS(y, x) 19.29/7.31 UNION(x, y) == UNION(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.31 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (44) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 U91^1(tt, A, B) -> PROD(A) 19.29/7.31 PROD(union(A, B)) -> U91^1(and(isBag(A), isBag(B)), A, B) 19.29/7.31 U91^1(tt, A, B) -> PROD(B) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 E# is empty. 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (45) EUsableRulesReductionPairsProof (EQUIVALENT) 19.29/7.31 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. 19.29/7.31 19.29/7.31 The following dependency pairs can be deleted: 19.29/7.31 19.29/7.31 U91^1(tt, A, B) -> PROD(A) 19.29/7.31 PROD(union(A, B)) -> U91^1(and(isBag(A), isBag(B)), A, B) 19.29/7.31 U91^1(tt, A, B) -> PROD(B) 19.29/7.31 The following rules are removed from R: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 The following equations are removed from E: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.31 19.29/7.31 POL(0(x_1)) = 3*x_1 19.29/7.31 POL(1(x_1)) = x_1 19.29/7.31 POL(PROD(x_1)) = 2 + 2*x_1 19.29/7.31 POL(U91^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 19.29/7.31 POL(and(x_1, x_2)) = 2 + 2*x_1 + x_2 19.29/7.31 POL(empty) = 2 19.29/7.31 POL(isBag(x_1)) = x_1 19.29/7.31 POL(isBin(x_1)) = 2*x_1 19.29/7.31 POL(mult(x_1, x_2)) = 2 + 3*x_1 + 2*x_2 19.29/7.31 POL(plus(x_1, x_2)) = 2 + 3*x_1 + 2*x_2 19.29/7.31 POL(prod(x_1)) = 3*x_1 19.29/7.31 POL(singl(x_1)) = 3*x_1 19.29/7.31 POL(sum(x_1)) = 3*x_1 19.29/7.31 POL(tt) = 2 19.29/7.31 POL(union(x_1, x_2)) = 3 + 3*x_1 + 3*x_2 19.29/7.31 POL(z) = 2 19.29/7.31 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (46) 19.29/7.31 Obligation: 19.29/7.31 P is empty. 19.29/7.31 R is empty. 19.29/7.31 E is empty. 19.29/7.31 E# is empty. 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (47) PisEmptyProof (EQUIVALENT) 19.29/7.31 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (48) 19.29/7.31 YES 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (49) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 SUM(union(A, B)) -> U111^1(and(isBag(A), isBag(B)), A, B) 19.29/7.31 U111^1(tt, A, B) -> SUM(B) 19.29/7.31 U111^1(tt, A, B) -> SUM(A) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 The set E# consists of the following equations: 19.29/7.31 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 PLUS(x, y) == PLUS(y, x) 19.29/7.31 UNION(x, y) == UNION(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.31 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.31 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (50) ESharpUsableEquationsProof (EQUIVALENT) 19.29/7.31 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 19.29/7.31 MULT(x, y) == MULT(y, x) 19.29/7.31 PLUS(x, y) == PLUS(y, x) 19.29/7.31 UNION(x, y) == UNION(y, x) 19.29/7.31 MULT(mult(x, y), z') == MULT(x, mult(y, z')) 19.29/7.31 PLUS(plus(x, y), z') == PLUS(x, plus(y, z')) 19.29/7.31 UNION(union(x, y), z') == UNION(x, union(y, z')) 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (51) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 SUM(union(A, B)) -> U111^1(and(isBag(A), isBag(B)), A, B) 19.29/7.31 U111^1(tt, A, B) -> SUM(B) 19.29/7.31 U111^1(tt, A, B) -> SUM(A) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 and(tt, X) -> X 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 19.29/7.31 The set E consists of the following equations: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 19.29/7.31 E# is empty. 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (52) EUsableRulesReductionPairsProof (EQUIVALENT) 19.29/7.31 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. 19.29/7.31 19.29/7.31 The following dependency pairs can be deleted: 19.29/7.31 19.29/7.31 SUM(union(A, B)) -> U111^1(and(isBag(A), isBag(B)), A, B) 19.29/7.31 The following rules are removed from R: 19.29/7.31 19.29/7.31 union(X, empty) -> X 19.29/7.31 union(empty, X) -> X 19.29/7.31 0(z) -> z 19.29/7.31 U101(tt, X) -> X 19.29/7.31 U11(tt) -> z 19.29/7.31 U111(tt, A, B) -> plus(sum(A), sum(B)) 19.29/7.31 U21(tt, X, Y) -> 0(mult(X, Y)) 19.29/7.31 U31(tt, X, Y) -> plus(0(mult(X, Y)), Y) 19.29/7.31 U41(tt, X) -> X 19.29/7.31 U51(tt, X, Y) -> 0(plus(X, Y)) 19.29/7.31 U61(tt, X, Y) -> 1(plus(X, Y)) 19.29/7.31 U71(tt, X, Y) -> 0(plus(plus(X, Y), 1(z))) 19.29/7.31 U81(tt, X) -> X 19.29/7.31 U91(tt, A, B) -> mult(prod(A), prod(B)) 19.29/7.31 isBag(empty) -> tt 19.29/7.31 isBag(singl(V1)) -> isBin(V1) 19.29/7.31 isBag(union(V1, V2)) -> and(isBag(V1), isBag(V2)) 19.29/7.31 isBin(z) -> tt 19.29/7.31 isBin(0(V1)) -> isBin(V1) 19.29/7.31 isBin(1(V1)) -> isBin(V1) 19.29/7.31 isBin(mult(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(plus(V1, V2)) -> and(isBin(V1), isBin(V2)) 19.29/7.31 isBin(prod(V1)) -> isBag(V1) 19.29/7.31 isBin(sum(V1)) -> isBag(V1) 19.29/7.31 mult(z, X) -> U11(isBin(X)) 19.29/7.31 mult(0(X), Y) -> U21(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 mult(1(X), Y) -> U31(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(z, X) -> U41(isBin(X), X) 19.29/7.31 plus(0(X), 0(Y)) -> U51(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(0(X), 1(Y)) -> U61(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 plus(1(X), 1(Y)) -> U71(and(isBin(X), isBin(Y)), X, Y) 19.29/7.31 prod(empty) -> 1(z) 19.29/7.31 prod(singl(X)) -> U81(isBin(X), X) 19.29/7.31 prod(union(A, B)) -> U91(and(isBag(A), isBag(B)), A, B) 19.29/7.31 sum(empty) -> 0(z) 19.29/7.31 sum(singl(X)) -> U101(isBin(X), X) 19.29/7.31 sum(union(A, B)) -> U111(and(isBag(A), isBag(B)), A, B) 19.29/7.31 mult(mult(z, X), ext) -> mult(U11(isBin(X)), ext) 19.29/7.31 mult(mult(0(X), Y), ext) -> mult(U21(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 mult(mult(1(X), Y), ext) -> mult(U31(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(z, X), ext) -> plus(U41(isBin(X), X), ext) 19.29/7.31 plus(plus(0(X), 0(Y)), ext) -> plus(U51(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(0(X), 1(Y)), ext) -> plus(U61(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 plus(plus(1(X), 1(Y)), ext) -> plus(U71(and(isBin(X), isBin(Y)), X, Y), ext) 19.29/7.31 The following equations are removed from E: 19.29/7.31 19.29/7.31 mult(x, y) == mult(y, x) 19.29/7.31 plus(x, y) == plus(y, x) 19.29/7.31 union(x, y) == union(y, x) 19.29/7.31 mult(mult(x, y), z') == mult(x, mult(y, z')) 19.29/7.31 plus(plus(x, y), z') == plus(x, plus(y, z')) 19.29/7.31 union(union(x, y), z') == union(x, union(y, z')) 19.29/7.31 Used ordering: POLO with Polynomial interpretation [POLO]: 19.29/7.31 19.29/7.31 POL(0(x_1)) = 3*x_1 19.29/7.31 POL(1(x_1)) = 3*x_1 19.29/7.31 POL(SUM(x_1)) = 2*x_1 19.29/7.31 POL(U111^1(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 19.29/7.31 POL(and(x_1, x_2)) = 2*x_1 + x_2 19.29/7.31 POL(empty) = 0 19.29/7.31 POL(isBag(x_1)) = 2 + 2*x_1 19.29/7.31 POL(isBin(x_1)) = 2*x_1 19.29/7.31 POL(mult(x_1, x_2)) = 3 + 3*x_1 + 2*x_2 19.29/7.31 POL(plus(x_1, x_2)) = 2 + 3*x_1 + 2*x_2 19.29/7.31 POL(prod(x_1)) = 1 + 3*x_1 19.29/7.31 POL(singl(x_1)) = 3 + 3*x_1 19.29/7.31 POL(sum(x_1)) = 2 + 3*x_1 19.29/7.31 POL(tt) = 0 19.29/7.31 POL(union(x_1, x_2)) = 3 + 3*x_1 + 3*x_2 19.29/7.31 POL(z) = 0 19.29/7.31 19.29/7.31 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (53) 19.29/7.31 Obligation: 19.29/7.31 The TRS P consists of the following rules: 19.29/7.31 19.29/7.31 U111^1(tt, A, B) -> SUM(B) 19.29/7.31 U111^1(tt, A, B) -> SUM(A) 19.29/7.31 19.29/7.31 The TRS R consists of the following rules: 19.29/7.31 19.29/7.31 and(tt, X) -> X 19.29/7.31 19.29/7.31 E is empty. 19.29/7.31 E# is empty. 19.29/7.31 We have to consider all minimal (P,E#,R,E)-chains 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (54) EDependencyGraphProof (EQUIVALENT) 19.29/7.31 The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 2 less nodes. 19.29/7.31 ---------------------------------------- 19.29/7.31 19.29/7.31 (55) 19.29/7.31 TRUE 19.40/7.38 EOF