27.87/15.23 YES 27.87/15.24 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 27.87/15.24 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 27.87/15.24 27.87/15.24 27.87/15.24 Termination of the given ETRS could be proven: 27.87/15.24 27.87/15.24 (0) ETRS 27.87/15.24 (1) EquationalDependencyPairsProof [EQUIVALENT, 12 ms] 27.87/15.24 (2) EDP 27.87/15.24 (3) EDependencyGraphProof [EQUIVALENT, 0 ms] 27.87/15.24 (4) AND 27.87/15.24 (5) EDP 27.87/15.24 (6) ESharpUsableEquationsProof [EQUIVALENT, 12 ms] 27.87/15.24 (7) EDP 27.87/15.24 (8) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 27.87/15.24 (9) EDP 27.87/15.24 (10) PisEmptyProof [EQUIVALENT, 0 ms] 27.87/15.24 (11) YES 27.87/15.24 (12) EDP 27.87/15.24 (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 27.87/15.24 (14) EDP 27.87/15.24 (15) EDPPoloProof [EQUIVALENT, 6 ms] 27.87/15.24 (16) EDP 27.87/15.24 (17) EDPPoloProof [EQUIVALENT, 6 ms] 27.87/15.24 (18) EDP 27.87/15.24 (19) PisEmptyProof [EQUIVALENT, 0 ms] 27.87/15.24 (20) YES 27.87/15.24 (21) EDP 27.87/15.24 (22) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 27.87/15.24 (23) EDP 27.87/15.24 (24) EDPPoloProof [EQUIVALENT, 905 ms] 27.87/15.24 (25) EDP 27.87/15.24 (26) EDependencyGraphProof [EQUIVALENT, 0 ms] 27.87/15.24 (27) EDP 27.87/15.24 (28) EDPPoloProof [EQUIVALENT, 1921 ms] 27.87/15.24 (29) EDP 27.87/15.24 (30) EDPPoloProof [EQUIVALENT, 852 ms] 27.87/15.24 (31) EDP 27.87/15.24 (32) PisEmptyProof [EQUIVALENT, 0 ms] 27.87/15.24 (33) YES 27.87/15.24 (34) EDP 27.87/15.24 (35) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 27.87/15.24 (36) EDP 27.87/15.24 (37) EDPPoloProof [EQUIVALENT, 1819 ms] 27.87/15.24 (38) EDP 27.87/15.24 (39) PisEmptyProof [EQUIVALENT, 0 ms] 27.87/15.24 (40) YES 27.87/15.24 27.87/15.24 27.87/15.24 ---------------------------------------- 27.87/15.24 27.87/15.24 (0) 27.87/15.24 Obligation: 27.87/15.24 Equational rewrite system: 27.87/15.24 The TRS R consists of the following rules: 27.87/15.24 27.87/15.24 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.24 U11(tt, A) -> A 27.87/15.24 U111(tt) -> false 27.87/15.24 U121(tt, A) -> A 27.87/15.24 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.24 U132(tt, U') -> U' 27.87/15.24 U141(tt, U) -> U 27.87/15.24 U151(tt, A) -> _xor_(A, true) 27.87/15.24 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.24 U31(tt) -> false 27.87/15.24 U41(tt, A) -> A 27.87/15.24 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.24 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.24 U62(tt) -> false 27.87/15.24 U71(tt) -> true 27.87/15.24 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.24 U91(tt) -> false 27.87/15.24 _and_(A, A) -> U11(isBool(A), A) 27.87/15.24 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.24 _and_(false, A) -> U31(isBool(A)) 27.87/15.24 _and_(true, A) -> U41(isBool(A), A) 27.87/15.24 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.24 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.24 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.24 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.24 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.24 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.24 _xor_(A, A) -> U111(isBool(A)) 27.87/15.24 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.24 and(tt, X) -> X 27.87/15.24 equal(X, X) -> tt 27.87/15.24 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.24 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.24 isBool(false) -> tt 27.87/15.24 isBool(true) -> tt 27.87/15.24 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.24 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.24 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.24 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.24 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.24 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.24 isBool(not_(V1)) -> isBool(V1) 27.87/15.24 not_(A) -> U151(isBool(A), A) 27.87/15.24 not_(false) -> true 27.87/15.24 not_(true) -> false 27.87/15.24 27.87/15.24 The set E consists of the following equations: 27.87/15.24 27.87/15.24 _and_(x, y) == _and_(y, x) 27.87/15.24 _or_(x, y) == _or_(y, x) 27.87/15.24 _xor_(x, y) == _xor_(y, x) 27.87/15.24 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.24 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.24 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.24 27.87/15.24 27.87/15.24 ---------------------------------------- 27.87/15.24 27.87/15.24 (1) EquationalDependencyPairsProof (EQUIVALENT) 27.87/15.24 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 27.87/15.24 The TRS P consists of the following rules: 27.87/15.24 27.87/15.24 U101^1(tt, A, B) -> _XOR_(_and_(A, B), _xor_(A, B)) 27.87/15.24 U101^1(tt, A, B) -> _AND_(A, B) 27.87/15.24 U101^1(tt, A, B) -> _XOR_(A, B) 27.87/15.24 U131^1(tt, B, U') -> U132^1(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.24 U131^1(tt, B, U') -> EQUAL(_isNotEqualTo_(B, true), true) 27.87/15.24 U131^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.87/15.24 U151^1(tt, A) -> _XOR_(A, true) 27.87/15.24 U21^1(tt, A, B, C) -> _XOR_(_and_(A, B), _and_(A, C)) 27.87/15.24 U21^1(tt, A, B, C) -> _AND_(A, B) 27.87/15.24 U21^1(tt, A, B, C) -> _AND_(A, C) 27.87/15.24 U51^1(tt, A, B) -> NOT_(_xor_(A, _and_(A, B))) 27.87/15.24 U51^1(tt, A, B) -> _XOR_(A, _and_(A, B)) 27.87/15.24 U51^1(tt, A, B) -> _AND_(A, B) 27.87/15.24 U61^1(tt, U', U) -> U62^1(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.24 U61^1(tt, U', U) -> EQUAL(_isNotEqualTo_(U, U'), true) 27.87/15.24 U61^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.87/15.24 U81^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.87/15.24 U81^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.87/15.24 _AND_(A, A) -> U11^1(isBool(A), A) 27.87/15.24 _AND_(A, A) -> ISBOOL(A) 27.87/15.24 _AND_(A, _xor_(B, C)) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.24 _AND_(A, _xor_(B, C)) -> AND(isBool(A), and(isBool(B), isBool(C))) 27.87/15.24 _AND_(A, _xor_(B, C)) -> ISBOOL(A) 27.87/15.24 _AND_(A, _xor_(B, C)) -> AND(isBool(B), isBool(C)) 27.87/15.24 _AND_(A, _xor_(B, C)) -> ISBOOL(B) 27.87/15.24 _AND_(A, _xor_(B, C)) -> ISBOOL(C) 27.87/15.24 _AND_(false, A) -> U31^1(isBool(A)) 27.87/15.24 _AND_(false, A) -> ISBOOL(A) 27.87/15.24 _AND_(true, A) -> U41^1(isBool(A), A) 27.87/15.24 _AND_(true, A) -> ISBOOL(A) 27.87/15.24 _IMPLIES_(A, B) -> U51^1(and(isBool(A), isBool(B)), A, B) 27.87/15.24 _IMPLIES_(A, B) -> AND(isBool(A), isBool(B)) 27.87/15.24 _IMPLIES_(A, B) -> ISBOOL(A) 27.87/15.24 _IMPLIES_(A, B) -> ISBOOL(B) 27.87/15.24 _ISEQUALTO_(U, U') -> U61^1(and(isS(U'), isS(U)), U', U) 27.87/15.24 _ISEQUALTO_(U, U') -> AND(isS(U'), isS(U)) 27.87/15.24 _ISEQUALTO_(U, U) -> U71^1(isS(U)) 27.87/15.24 _ISNOTEQUALTO_(U, U') -> U81^1(and(isS(U'), isS(U)), U', U) 27.87/15.24 _ISNOTEQUALTO_(U, U') -> AND(isS(U'), isS(U)) 27.87/15.24 _ISNOTEQUALTO_(U, U) -> U91^1(isS(U)) 27.87/15.24 _OR_(A, B) -> U101^1(and(isBool(A), isBool(B)), A, B) 27.87/15.24 _OR_(A, B) -> AND(isBool(A), isBool(B)) 27.87/15.24 _OR_(A, B) -> ISBOOL(A) 27.87/15.24 _OR_(A, B) -> ISBOOL(B) 27.87/15.24 _XOR_(A, A) -> U111^1(isBool(A)) 27.87/15.24 _XOR_(A, A) -> ISBOOL(A) 27.87/15.24 _XOR_(false, A) -> U121^1(isBool(A), A) 27.87/15.24 _XOR_(false, A) -> ISBOOL(A) 27.87/15.24 IF_THEN_ELSE_FI(B, U, U') -> U131^1(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.24 IF_THEN_ELSE_FI(B, U, U') -> AND(isBool(B), and(isS(U'), isS(U))) 27.87/15.24 IF_THEN_ELSE_FI(B, U, U') -> ISBOOL(B) 27.87/15.24 IF_THEN_ELSE_FI(B, U, U') -> AND(isS(U'), isS(U)) 27.87/15.24 IF_THEN_ELSE_FI(true, U, U') -> U141^1(and(isS(U'), isS(U)), U) 27.87/15.24 IF_THEN_ELSE_FI(true, U, U') -> AND(isS(U'), isS(U)) 27.87/15.24 ISBOOL(_and_(V1, V2)) -> AND(isBool(V1), isBool(V2)) 27.87/15.24 ISBOOL(_and_(V1, V2)) -> ISBOOL(V1) 27.87/15.24 ISBOOL(_and_(V1, V2)) -> ISBOOL(V2) 27.87/15.24 ISBOOL(_implies_(V1, V2)) -> AND(isBool(V1), isBool(V2)) 27.87/15.24 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1) 27.87/15.24 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V2) 27.87/15.24 ISBOOL(_isEqualTo_(V1, V2)) -> AND(isUniversal(V1), isUniversal(V2)) 27.87/15.24 ISBOOL(_isNotEqualTo_(V1, V2)) -> AND(isUniversal(V1), isUniversal(V2)) 27.87/15.24 ISBOOL(_or_(V1, V2)) -> AND(isBool(V1), isBool(V2)) 27.87/15.24 ISBOOL(_or_(V1, V2)) -> ISBOOL(V1) 27.87/15.24 ISBOOL(_or_(V1, V2)) -> ISBOOL(V2) 27.87/15.24 ISBOOL(_xor_(V1, V2)) -> AND(isBool(V1), isBool(V2)) 27.87/15.24 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1) 27.87/15.24 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V2) 27.87/15.24 ISBOOL(not_(V1)) -> ISBOOL(V1) 27.87/15.24 NOT_(A) -> U151^1(isBool(A), A) 27.87/15.24 NOT_(A) -> ISBOOL(A) 27.87/15.24 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.24 _AND_(_and_(A, A), ext) -> U11^1(isBool(A), A) 27.87/15.24 _AND_(_and_(A, A), ext) -> ISBOOL(A) 27.87/15.24 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.24 _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.24 _AND_(_and_(A, _xor_(B, C)), ext) -> AND(isBool(A), and(isBool(B), isBool(C))) 27.87/15.24 _AND_(_and_(A, _xor_(B, C)), ext) -> ISBOOL(A) 27.87/15.24 _AND_(_and_(A, _xor_(B, C)), ext) -> AND(isBool(B), isBool(C)) 27.87/15.24 _AND_(_and_(A, _xor_(B, C)), ext) -> ISBOOL(B) 27.87/15.24 _AND_(_and_(A, _xor_(B, C)), ext) -> ISBOOL(C) 27.87/15.24 _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext) 27.87/15.24 _AND_(_and_(false, A), ext) -> U31^1(isBool(A)) 27.87/15.24 _AND_(_and_(false, A), ext) -> ISBOOL(A) 27.87/15.24 _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(true, A), ext) -> U41^1(isBool(A), A) 27.87/15.25 _AND_(_and_(true, A), ext) -> ISBOOL(A) 27.87/15.25 _OR_(_or_(A, B), ext) -> _OR_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _OR_(_or_(A, B), ext) -> U101^1(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _OR_(_or_(A, B), ext) -> AND(isBool(A), isBool(B)) 27.87/15.25 _OR_(_or_(A, B), ext) -> ISBOOL(A) 27.87/15.25 _OR_(_or_(A, B), ext) -> ISBOOL(B) 27.87/15.25 _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext) 27.87/15.25 _XOR_(_xor_(A, A), ext) -> U111^1(isBool(A)) 27.87/15.25 _XOR_(_xor_(A, A), ext) -> ISBOOL(A) 27.87/15.25 _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext) 27.87/15.25 _XOR_(_xor_(false, A), ext) -> U121^1(isBool(A), A) 27.87/15.25 _XOR_(_xor_(false, A), ext) -> ISBOOL(A) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 _OR_(x, y) == _OR_(y, x) 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (2) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 U101^1(tt, A, B) -> _XOR_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U101^1(tt, A, B) -> _AND_(A, B) 27.87/15.25 U101^1(tt, A, B) -> _XOR_(A, B) 27.87/15.25 U131^1(tt, B, U') -> U132^1(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U131^1(tt, B, U') -> EQUAL(_isNotEqualTo_(B, true), true) 27.87/15.25 U131^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.87/15.25 U151^1(tt, A) -> _XOR_(A, true) 27.87/15.25 U21^1(tt, A, B, C) -> _XOR_(_and_(A, B), _and_(A, C)) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, B) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, C) 27.87/15.25 U51^1(tt, A, B) -> NOT_(_xor_(A, _and_(A, B))) 27.87/15.25 U51^1(tt, A, B) -> _XOR_(A, _and_(A, B)) 27.87/15.25 U51^1(tt, A, B) -> _AND_(A, B) 27.87/15.25 U61^1(tt, U', U) -> U62^1(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U61^1(tt, U', U) -> EQUAL(_isNotEqualTo_(U, U'), true) 27.87/15.25 U61^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.87/15.25 U81^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.87/15.25 U81^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.87/15.25 _AND_(A, A) -> U11^1(isBool(A), A) 27.87/15.25 _AND_(A, A) -> ISBOOL(A) 27.87/15.25 _AND_(A, _xor_(B, C)) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _AND_(A, _xor_(B, C)) -> AND(isBool(A), and(isBool(B), isBool(C))) 27.87/15.25 _AND_(A, _xor_(B, C)) -> ISBOOL(A) 27.87/15.25 _AND_(A, _xor_(B, C)) -> AND(isBool(B), isBool(C)) 27.87/15.25 _AND_(A, _xor_(B, C)) -> ISBOOL(B) 27.87/15.25 _AND_(A, _xor_(B, C)) -> ISBOOL(C) 27.87/15.25 _AND_(false, A) -> U31^1(isBool(A)) 27.87/15.25 _AND_(false, A) -> ISBOOL(A) 27.87/15.25 _AND_(true, A) -> U41^1(isBool(A), A) 27.87/15.25 _AND_(true, A) -> ISBOOL(A) 27.87/15.25 _IMPLIES_(A, B) -> U51^1(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _IMPLIES_(A, B) -> AND(isBool(A), isBool(B)) 27.87/15.25 _IMPLIES_(A, B) -> ISBOOL(A) 27.87/15.25 _IMPLIES_(A, B) -> ISBOOL(B) 27.87/15.25 _ISEQUALTO_(U, U') -> U61^1(and(isS(U'), isS(U)), U', U) 27.87/15.25 _ISEQUALTO_(U, U') -> AND(isS(U'), isS(U)) 27.87/15.25 _ISEQUALTO_(U, U) -> U71^1(isS(U)) 27.87/15.25 _ISNOTEQUALTO_(U, U') -> U81^1(and(isS(U'), isS(U)), U', U) 27.87/15.25 _ISNOTEQUALTO_(U, U') -> AND(isS(U'), isS(U)) 27.87/15.25 _ISNOTEQUALTO_(U, U) -> U91^1(isS(U)) 27.87/15.25 _OR_(A, B) -> U101^1(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _OR_(A, B) -> AND(isBool(A), isBool(B)) 27.87/15.25 _OR_(A, B) -> ISBOOL(A) 27.87/15.25 _OR_(A, B) -> ISBOOL(B) 27.87/15.25 _XOR_(A, A) -> U111^1(isBool(A)) 27.87/15.25 _XOR_(A, A) -> ISBOOL(A) 27.87/15.25 _XOR_(false, A) -> U121^1(isBool(A), A) 27.87/15.25 _XOR_(false, A) -> ISBOOL(A) 27.87/15.25 IF_THEN_ELSE_FI(B, U, U') -> U131^1(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 IF_THEN_ELSE_FI(B, U, U') -> AND(isBool(B), and(isS(U'), isS(U))) 27.87/15.25 IF_THEN_ELSE_FI(B, U, U') -> ISBOOL(B) 27.87/15.25 IF_THEN_ELSE_FI(B, U, U') -> AND(isS(U'), isS(U)) 27.87/15.25 IF_THEN_ELSE_FI(true, U, U') -> U141^1(and(isS(U'), isS(U)), U) 27.87/15.25 IF_THEN_ELSE_FI(true, U, U') -> AND(isS(U'), isS(U)) 27.87/15.25 ISBOOL(_and_(V1, V2)) -> AND(isBool(V1), isBool(V2)) 27.87/15.25 ISBOOL(_and_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_and_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_implies_(V1, V2)) -> AND(isBool(V1), isBool(V2)) 27.87/15.25 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_isEqualTo_(V1, V2)) -> AND(isUniversal(V1), isUniversal(V2)) 27.87/15.25 ISBOOL(_isNotEqualTo_(V1, V2)) -> AND(isUniversal(V1), isUniversal(V2)) 27.87/15.25 ISBOOL(_or_(V1, V2)) -> AND(isBool(V1), isBool(V2)) 27.87/15.25 ISBOOL(_or_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_or_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_xor_(V1, V2)) -> AND(isBool(V1), isBool(V2)) 27.87/15.25 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(not_(V1)) -> ISBOOL(V1) 27.87/15.25 NOT_(A) -> U151^1(isBool(A), A) 27.87/15.25 NOT_(A) -> ISBOOL(A) 27.87/15.25 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(A, A), ext) -> U11^1(isBool(A), A) 27.87/15.25 _AND_(_and_(A, A), ext) -> ISBOOL(A) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> AND(isBool(A), and(isBool(B), isBool(C))) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> ISBOOL(A) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> AND(isBool(B), isBool(C)) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> ISBOOL(B) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> ISBOOL(C) 27.87/15.25 _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext) 27.87/15.25 _AND_(_and_(false, A), ext) -> U31^1(isBool(A)) 27.87/15.25 _AND_(_and_(false, A), ext) -> ISBOOL(A) 27.87/15.25 _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(true, A), ext) -> U41^1(isBool(A), A) 27.87/15.25 _AND_(_and_(true, A), ext) -> ISBOOL(A) 27.87/15.25 _OR_(_or_(A, B), ext) -> _OR_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _OR_(_or_(A, B), ext) -> U101^1(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _OR_(_or_(A, B), ext) -> AND(isBool(A), isBool(B)) 27.87/15.25 _OR_(_or_(A, B), ext) -> ISBOOL(A) 27.87/15.25 _OR_(_or_(A, B), ext) -> ISBOOL(B) 27.87/15.25 _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext) 27.87/15.25 _XOR_(_xor_(A, A), ext) -> U111^1(isBool(A)) 27.87/15.25 _XOR_(_xor_(A, A), ext) -> ISBOOL(A) 27.87/15.25 _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext) 27.87/15.25 _XOR_(_xor_(false, A), ext) -> U121^1(isBool(A), A) 27.87/15.25 _XOR_(_xor_(false, A), ext) -> ISBOOL(A) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 _OR_(x, y) == _OR_(y, x) 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (3) EDependencyGraphProof (EQUIVALENT) 27.87/15.25 The approximation of the Equational Dependency Graph [DA_STEIN] contains 4 SCCs with 78 less nodes. 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (4) 27.87/15.25 Complex Obligation (AND) 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (5) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 ISBOOL(_and_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(not_(V1)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_and_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_or_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_or_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 _OR_(x, y) == _OR_(y, x) 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (6) ESharpUsableEquationsProof (EQUIVALENT) 27.87/15.25 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 _OR_(x, y) == _OR_(y, x) 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (7) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 ISBOOL(_and_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(not_(V1)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_and_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_or_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_or_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 E# is empty. 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (8) EUsableRulesReductionPairsProof (EQUIVALENT) 27.87/15.25 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. 27.87/15.25 27.87/15.25 The following dependency pairs can be deleted: 27.87/15.25 27.87/15.25 ISBOOL(_and_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_implies_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(not_(V1)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_and_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_or_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_or_(V1, V2)) -> ISBOOL(V2) 27.87/15.25 ISBOOL(_xor_(V1, V2)) -> ISBOOL(V1) 27.87/15.25 The following rules are removed from R: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 The following equations are removed from E: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 Used ordering: POLO with Polynomial interpretation [POLO]: 27.87/15.25 27.87/15.25 POL(ISBOOL(x_1)) = 2*x_1 27.87/15.25 POL(_and_(x_1, x_2)) = 3*x_1 + x_2 27.87/15.25 POL(_implies_(x_1, x_2)) = 3*x_1 + 3*x_2 27.87/15.25 POL(_or_(x_1, x_2)) = 3*x_1 + x_2 27.87/15.25 POL(_xor_(x_1, x_2)) = 3*x_1 + 3*x_2 27.87/15.25 POL(not_(x_1)) = 3*x_1 27.87/15.25 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (9) 27.87/15.25 Obligation: 27.87/15.25 P is empty. 27.87/15.25 R is empty. 27.87/15.25 E is empty. 27.87/15.25 E# is empty. 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (10) PisEmptyProof (EQUIVALENT) 27.87/15.25 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (11) 27.87/15.25 YES 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (12) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext) 27.87/15.25 _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 _OR_(x, y) == _OR_(y, x) 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (13) ESharpUsableEquationsProof (EQUIVALENT) 27.87/15.25 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 _OR_(x, y) == _OR_(y, x) 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (14) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext) 27.87/15.25 _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (15) EDPPoloProof (EQUIVALENT) 27.87/15.25 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. 27.87/15.25 27.87/15.25 27.87/15.25 _XOR_(_xor_(false, A), ext) -> _XOR_(U121(isBool(A), A), ext) 27.87/15.25 The remaining Dependency Pairs were at least non-strictly oriented. 27.87/15.25 27.87/15.25 27.87/15.25 _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext) 27.87/15.25 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 27.87/15.25 27.87/15.25 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 and(tt, X) -> X 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 We had to orient the following equations of E# equivalently. 27.87/15.25 27.87/15.25 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 With the implicit AFS we had to orient the following usable equations of E equivalently. 27.87/15.25 27.87/15.25 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 Used ordering: POLO with Polynomial interpretation [POLO]: 27.87/15.25 27.87/15.25 POL(U111(x_1)) = 3*x_1 27.87/15.25 POL(U121(x_1, x_2)) = 2 + x_1 + x_2 27.87/15.25 POL(_XOR_(x_1, x_2)) = 3*x_1 + 3*x_2 27.87/15.25 POL(_and_(x_1, x_2)) = 0 27.87/15.25 POL(_implies_(x_1, x_2)) = 0 27.87/15.25 POL(_isEqualTo_(x_1, x_2)) = 0 27.87/15.25 POL(_isNotEqualTo_(x_1, x_2)) = 0 27.87/15.25 POL(_or_(x_1, x_2)) = 0 27.87/15.25 POL(_xor_(x_1, x_2)) = 3 + x_1 + x_2 27.87/15.25 POL(and(x_1, x_2)) = x_2 27.87/15.25 POL(false) = 3 27.87/15.25 POL(isBool(x_1)) = 1 27.87/15.25 POL(isUniversal(x_1)) = 0 27.87/15.25 POL(not_(x_1)) = 0 27.87/15.25 POL(true) = 0 27.87/15.25 POL(tt) = 1 27.87/15.25 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (16) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (17) EDPPoloProof (EQUIVALENT) 27.87/15.25 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 27.87/15.25 27.87/15.25 27.87/15.25 _XOR_(_xor_(A, A), ext) -> _XOR_(U111(isBool(A)), ext) 27.87/15.25 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 27.87/15.25 27.87/15.25 27.87/15.25 U111(tt) -> false 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 U121(tt, A) -> A 27.87/15.25 We had to orient the following equations of E# equivalently. 27.87/15.25 27.87/15.25 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 With the implicit AFS we had to orient the following usable equations of E equivalently. 27.87/15.25 27.87/15.25 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 Used ordering: POLO with Polynomial interpretation [POLO]: 27.87/15.25 27.87/15.25 POL(U111(x_1)) = 0 27.87/15.25 POL(U121(x_1, x_2)) = x_2 27.87/15.25 POL(_XOR_(x_1, x_2)) = x_1 + x_2 27.87/15.25 POL(_and_(x_1, x_2)) = 2*x_1 + 2*x_2 27.87/15.25 POL(_implies_(x_1, x_2)) = 2 + x_1 + 2*x_2 27.87/15.25 POL(_isEqualTo_(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 27.87/15.25 POL(_isNotEqualTo_(x_1, x_2)) = 2 + 2*x_1 + x_2 27.87/15.25 POL(_or_(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 27.87/15.25 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 27.87/15.25 POL(and(x_1, x_2)) = x_2 27.87/15.25 POL(false) = 0 27.87/15.25 POL(isBool(x_1)) = x_1 27.87/15.25 POL(isUniversal(x_1)) = 0 27.87/15.25 POL(not_(x_1)) = 2*x_1 27.87/15.25 POL(true) = 0 27.87/15.25 POL(tt) = 0 27.87/15.25 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (18) 27.87/15.25 Obligation: 27.87/15.25 P is empty. 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (19) PisEmptyProof (EQUIVALENT) 27.87/15.25 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (20) 27.87/15.25 YES 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (21) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, B) 27.87/15.25 _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext) 27.87/15.25 _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, C) 27.87/15.25 _AND_(A, _xor_(B, C)) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 _OR_(x, y) == _OR_(y, x) 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (22) ESharpUsableEquationsProof (EQUIVALENT) 27.87/15.25 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 27.87/15.25 _OR_(x, y) == _OR_(y, x) 27.87/15.25 _XOR_(x, y) == _XOR_(y, x) 27.87/15.25 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.25 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (23) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, B) 27.87/15.25 _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext) 27.87/15.25 _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, C) 27.87/15.25 _AND_(A, _xor_(B, C)) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (24) EDPPoloProof (EQUIVALENT) 27.87/15.25 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. 27.87/15.25 27.87/15.25 27.87/15.25 _AND_(_and_(true, A), ext) -> _AND_(U41(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _AND_(A, _xor_(B, C)) -> U21^1(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 The remaining Dependency Pairs were at least non-strictly oriented. 27.87/15.25 27.87/15.25 27.87/15.25 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, B) 27.87/15.25 _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, C) 27.87/15.25 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 27.87/15.25 27.87/15.25 27.87/15.25 U31(tt) -> false 27.87/15.25 and(tt, X) -> X 27.87/15.25 U121(tt, A) -> A 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 U111(tt) -> false 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 U41(tt, A) -> A 27.87/15.25 We had to orient the following equations of E# equivalently. 27.87/15.25 27.87/15.25 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 With the implicit AFS we had to orient the following usable equations of E equivalently. 27.87/15.25 27.87/15.25 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 Used ordering: POLO with Polynomial interpretation [POLO]: 27.87/15.25 27.87/15.25 POL(U11(x_1, x_2)) = x_1*x_2 + x_2 27.87/15.25 POL(U111(x_1)) = 0 27.87/15.25 POL(U121(x_1, x_2)) = x_2 27.87/15.25 POL(U21(x_1, x_2, x_3, x_4)) = 1 + x_1*x_2 + x_1*x_2*x_4 + x_2 + x_2*x_3 + x_3 + x_4 27.87/15.25 POL(U21^1(x_1, x_2, x_3, x_4)) = x_2 + x_2*x_3 + x_2*x_4 + x_3 + x_4 27.87/15.25 POL(U31(x_1)) = 0 27.87/15.25 POL(U41(x_1, x_2)) = x_2 27.87/15.25 POL(_AND_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 27.87/15.25 POL(_and_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 27.87/15.25 POL(_implies_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 27.87/15.25 POL(_isEqualTo_(x_1, x_2)) = x_1*x_2 27.87/15.25 POL(_isNotEqualTo_(x_1, x_2)) = x_1*x_2 27.87/15.25 POL(_or_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 27.87/15.25 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 27.87/15.25 POL(and(x_1, x_2)) = x_1*x_2 27.87/15.25 POL(false) = 0 27.87/15.25 POL(isBool(x_1)) = 1 27.87/15.25 POL(isUniversal(x_1)) = 0 27.87/15.25 POL(not_(x_1)) = 1 + x_1 + x_1^2 27.87/15.25 POL(true) = 1 27.87/15.25 POL(tt) = 1 27.87/15.25 27.87/15.25 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (25) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, B) 27.87/15.25 _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext) 27.87/15.25 U21^1(tt, A, B, C) -> _AND_(A, C) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.25 U62(tt) -> false 27.87/15.25 U71(tt) -> true 27.87/15.25 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.25 U91(tt) -> false 27.87/15.25 _and_(A, A) -> U11(isBool(A), A) 27.87/15.25 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.25 _and_(false, A) -> U31(isBool(A)) 27.87/15.25 _and_(true, A) -> U41(isBool(A), A) 27.87/15.25 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.25 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.25 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.25 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.25 _xor_(A, A) -> U111(isBool(A)) 27.87/15.25 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.25 and(tt, X) -> X 27.87/15.25 equal(X, X) -> tt 27.87/15.25 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.25 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.25 isBool(false) -> tt 27.87/15.25 isBool(true) -> tt 27.87/15.25 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.25 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.25 isBool(not_(V1)) -> isBool(V1) 27.87/15.25 not_(A) -> U151(isBool(A), A) 27.87/15.25 not_(false) -> true 27.87/15.25 not_(true) -> false 27.87/15.25 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.25 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.25 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.25 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.25 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.25 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.25 27.87/15.25 The set E consists of the following equations: 27.87/15.25 27.87/15.25 _and_(x, y) == _and_(y, x) 27.87/15.25 _or_(x, y) == _or_(y, x) 27.87/15.25 _xor_(x, y) == _xor_(y, x) 27.87/15.25 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.25 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.25 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.25 27.87/15.25 The set E# consists of the following equations: 27.87/15.25 27.87/15.25 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.25 _AND_(x, y) == _AND_(y, x) 27.87/15.25 27.87/15.25 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (26) EDependencyGraphProof (EQUIVALENT) 27.87/15.25 The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 2 less nodes. 27.87/15.25 ---------------------------------------- 27.87/15.25 27.87/15.25 (27) 27.87/15.25 Obligation: 27.87/15.25 The TRS P consists of the following rules: 27.87/15.25 27.87/15.25 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.25 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.25 _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext) 27.87/15.25 27.87/15.25 The TRS R consists of the following rules: 27.87/15.25 27.87/15.25 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.25 U11(tt, A) -> A 27.87/15.25 U111(tt) -> false 27.87/15.25 U121(tt, A) -> A 27.87/15.25 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.25 U132(tt, U') -> U' 27.87/15.25 U141(tt, U) -> U 27.87/15.25 U151(tt, A) -> _xor_(A, true) 27.87/15.25 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.25 U31(tt) -> false 27.87/15.25 U41(tt, A) -> A 27.87/15.25 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.25 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.26 U62(tt) -> false 27.87/15.26 U71(tt) -> true 27.87/15.26 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.26 U91(tt) -> false 27.87/15.26 _and_(A, A) -> U11(isBool(A), A) 27.87/15.26 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.26 _and_(false, A) -> U31(isBool(A)) 27.87/15.26 _and_(true, A) -> U41(isBool(A), A) 27.87/15.26 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.26 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.26 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _xor_(A, A) -> U111(isBool(A)) 27.87/15.26 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.26 and(tt, X) -> X 27.87/15.26 equal(X, X) -> tt 27.87/15.26 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.26 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.26 isBool(false) -> tt 27.87/15.26 isBool(true) -> tt 27.87/15.26 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(not_(V1)) -> isBool(V1) 27.87/15.26 not_(A) -> U151(isBool(A), A) 27.87/15.26 not_(false) -> true 27.87/15.26 not_(true) -> false 27.87/15.26 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.26 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.26 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.26 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.26 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.26 27.87/15.26 The set E consists of the following equations: 27.87/15.26 27.87/15.26 _and_(x, y) == _and_(y, x) 27.87/15.26 _or_(x, y) == _or_(y, x) 27.87/15.26 _xor_(x, y) == _xor_(y, x) 27.87/15.26 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.26 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.26 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.26 27.87/15.26 The set E# consists of the following equations: 27.87/15.26 27.87/15.26 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.26 _AND_(x, y) == _AND_(y, x) 27.87/15.26 27.87/15.26 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (28) EDPPoloProof (EQUIVALENT) 27.87/15.26 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. 27.87/15.26 27.87/15.26 27.87/15.26 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _AND_(_and_(false, A), ext) -> _AND_(U31(isBool(A)), ext) 27.87/15.26 The remaining Dependency Pairs were at least non-strictly oriented. 27.87/15.26 27.87/15.26 27.87/15.26 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.26 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 27.87/15.26 27.87/15.26 27.87/15.26 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.26 U41(tt, A) -> A 27.87/15.26 _and_(false, A) -> U31(isBool(A)) 27.87/15.26 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.26 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.26 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.26 _and_(A, A) -> U11(isBool(A), A) 27.87/15.26 _and_(true, A) -> U41(isBool(A), A) 27.87/15.26 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.26 U111(tt) -> false 27.87/15.26 U11(tt, A) -> A 27.87/15.26 and(tt, X) -> X 27.87/15.26 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.26 _xor_(A, A) -> U111(isBool(A)) 27.87/15.26 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.26 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.26 U31(tt) -> false 27.87/15.26 isBool(true) -> tt 27.87/15.26 isBool(false) -> tt 27.87/15.26 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(not_(V1)) -> isBool(V1) 27.87/15.26 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 U121(tt, A) -> A 27.87/15.26 We had to orient the following equations of E# equivalently. 27.87/15.26 27.87/15.26 27.87/15.26 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.26 _AND_(x, y) == _AND_(y, x) 27.87/15.26 With the implicit AFS we had to orient the following usable equations of E equivalently. 27.87/15.26 27.87/15.26 27.87/15.26 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.26 _and_(x, y) == _and_(y, x) 27.87/15.26 _xor_(x, y) == _xor_(y, x) 27.87/15.26 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.26 Used ordering: POLO with Polynomial interpretation [POLO]: 27.87/15.26 27.87/15.26 POL(U11(x_1, x_2)) = 1 + x_2 27.87/15.26 POL(U111(x_1)) = 0 27.87/15.26 POL(U121(x_1, x_2)) = x_2 27.87/15.26 POL(U21(x_1, x_2, x_3, x_4)) = 2*x_1 + 2*x_1*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + 2*x_3 + 2*x_4 27.87/15.26 POL(U31(x_1)) = 0 27.87/15.26 POL(U41(x_1, x_2)) = 1 + x_2 27.87/15.26 POL(_AND_(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + 2*x_2 27.87/15.26 POL(_and_(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2 27.87/15.26 POL(_implies_(x_1, x_2)) = 0 27.87/15.26 POL(_isEqualTo_(x_1, x_2)) = 0 27.87/15.26 POL(_isNotEqualTo_(x_1, x_2)) = 0 27.87/15.26 POL(_or_(x_1, x_2)) = 0 27.87/15.26 POL(_xor_(x_1, x_2)) = 2 + x_1 + x_2 27.87/15.26 POL(and(x_1, x_2)) = x_2 27.87/15.26 POL(false) = 0 27.87/15.26 POL(isBool(x_1)) = 2 27.87/15.26 POL(isUniversal(x_1)) = 0 27.87/15.26 POL(not_(x_1)) = 0 27.87/15.26 POL(true) = 0 27.87/15.26 POL(tt) = 2 27.87/15.26 27.87/15.26 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (29) 27.87/15.26 Obligation: 27.87/15.26 The TRS P consists of the following rules: 27.87/15.26 27.87/15.26 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.26 27.87/15.26 The TRS R consists of the following rules: 27.87/15.26 27.87/15.26 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.26 U11(tt, A) -> A 27.87/15.26 U111(tt) -> false 27.87/15.26 U121(tt, A) -> A 27.87/15.26 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.26 U132(tt, U') -> U' 27.87/15.26 U141(tt, U) -> U 27.87/15.26 U151(tt, A) -> _xor_(A, true) 27.87/15.26 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.26 U31(tt) -> false 27.87/15.26 U41(tt, A) -> A 27.87/15.26 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.26 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.26 U62(tt) -> false 27.87/15.26 U71(tt) -> true 27.87/15.26 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.26 U91(tt) -> false 27.87/15.26 _and_(A, A) -> U11(isBool(A), A) 27.87/15.26 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.26 _and_(false, A) -> U31(isBool(A)) 27.87/15.26 _and_(true, A) -> U41(isBool(A), A) 27.87/15.26 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.26 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.26 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _xor_(A, A) -> U111(isBool(A)) 27.87/15.26 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.26 and(tt, X) -> X 27.87/15.26 equal(X, X) -> tt 27.87/15.26 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.26 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.26 isBool(false) -> tt 27.87/15.26 isBool(true) -> tt 27.87/15.26 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(not_(V1)) -> isBool(V1) 27.87/15.26 not_(A) -> U151(isBool(A), A) 27.87/15.26 not_(false) -> true 27.87/15.26 not_(true) -> false 27.87/15.26 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.26 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.26 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.26 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.26 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.26 27.87/15.26 The set E consists of the following equations: 27.87/15.26 27.87/15.26 _and_(x, y) == _and_(y, x) 27.87/15.26 _or_(x, y) == _or_(y, x) 27.87/15.26 _xor_(x, y) == _xor_(y, x) 27.87/15.26 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.26 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.26 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.26 27.87/15.26 The set E# consists of the following equations: 27.87/15.26 27.87/15.26 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.26 _AND_(x, y) == _AND_(y, x) 27.87/15.26 27.87/15.26 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (30) EDPPoloProof (EQUIVALENT) 27.87/15.26 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 27.87/15.26 27.87/15.26 27.87/15.26 _AND_(_and_(A, A), ext) -> _AND_(U11(isBool(A), A), ext) 27.87/15.26 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 27.87/15.26 27.87/15.26 27.87/15.26 U31(tt) -> false 27.87/15.26 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.26 U121(tt, A) -> A 27.87/15.26 U41(tt, A) -> A 27.87/15.26 and(tt, X) -> X 27.87/15.26 _and_(false, A) -> U31(isBool(A)) 27.87/15.26 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.26 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.26 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.26 _and_(A, A) -> U11(isBool(A), A) 27.87/15.26 _and_(true, A) -> U41(isBool(A), A) 27.87/15.26 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.26 U11(tt, A) -> A 27.87/15.26 isBool(true) -> tt 27.87/15.26 isBool(false) -> tt 27.87/15.26 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(not_(V1)) -> isBool(V1) 27.87/15.26 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.26 _xor_(A, A) -> U111(isBool(A)) 27.87/15.26 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.26 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.26 U111(tt) -> false 27.87/15.26 We had to orient the following equations of E# equivalently. 27.87/15.26 27.87/15.26 27.87/15.26 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.26 _AND_(x, y) == _AND_(y, x) 27.87/15.26 With the implicit AFS we had to orient the following usable equations of E equivalently. 27.87/15.26 27.87/15.26 27.87/15.26 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.26 _and_(x, y) == _and_(y, x) 27.87/15.26 _xor_(x, y) == _xor_(y, x) 27.87/15.26 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.26 Used ordering: POLO with Polynomial interpretation [POLO]: 27.87/15.26 27.87/15.26 POL(U11(x_1, x_2)) = x_1*x_2 27.87/15.26 POL(U111(x_1)) = 1 27.87/15.26 POL(U121(x_1, x_2)) = 1 + x_2 27.87/15.26 POL(U21(x_1, x_2, x_3, x_4)) = 3 + 2*x_1*x_2 + 2*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + 2*x_3 + 2*x_4 27.87/15.26 POL(U31(x_1)) = 0 27.87/15.26 POL(U41(x_1, x_2)) = x_1*x_2 27.87/15.26 POL(_AND_(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + 2*x_2 27.87/15.26 POL(_and_(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2 27.87/15.26 POL(_implies_(x_1, x_2)) = 0 27.87/15.26 POL(_isEqualTo_(x_1, x_2)) = 0 27.87/15.26 POL(_isNotEqualTo_(x_1, x_2)) = 0 27.87/15.26 POL(_or_(x_1, x_2)) = 0 27.87/15.26 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 27.87/15.26 POL(and(x_1, x_2)) = x_1*x_2 27.87/15.26 POL(false) = 0 27.87/15.26 POL(isBool(x_1)) = 1 27.87/15.26 POL(isUniversal(x_1)) = 1 27.87/15.26 POL(not_(x_1)) = 0 27.87/15.26 POL(true) = 0 27.87/15.26 POL(tt) = 1 27.87/15.26 27.87/15.26 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (31) 27.87/15.26 Obligation: 27.87/15.26 P is empty. 27.87/15.26 The TRS R consists of the following rules: 27.87/15.26 27.87/15.26 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.26 U11(tt, A) -> A 27.87/15.26 U111(tt) -> false 27.87/15.26 U121(tt, A) -> A 27.87/15.26 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.26 U132(tt, U') -> U' 27.87/15.26 U141(tt, U) -> U 27.87/15.26 U151(tt, A) -> _xor_(A, true) 27.87/15.26 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.26 U31(tt) -> false 27.87/15.26 U41(tt, A) -> A 27.87/15.26 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.26 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.26 U62(tt) -> false 27.87/15.26 U71(tt) -> true 27.87/15.26 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.26 U91(tt) -> false 27.87/15.26 _and_(A, A) -> U11(isBool(A), A) 27.87/15.26 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.26 _and_(false, A) -> U31(isBool(A)) 27.87/15.26 _and_(true, A) -> U41(isBool(A), A) 27.87/15.26 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.26 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.26 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _xor_(A, A) -> U111(isBool(A)) 27.87/15.26 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.26 and(tt, X) -> X 27.87/15.26 equal(X, X) -> tt 27.87/15.26 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.26 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.26 isBool(false) -> tt 27.87/15.26 isBool(true) -> tt 27.87/15.26 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(not_(V1)) -> isBool(V1) 27.87/15.26 not_(A) -> U151(isBool(A), A) 27.87/15.26 not_(false) -> true 27.87/15.26 not_(true) -> false 27.87/15.26 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.26 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.26 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.26 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.26 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.26 27.87/15.26 The set E consists of the following equations: 27.87/15.26 27.87/15.26 _and_(x, y) == _and_(y, x) 27.87/15.26 _or_(x, y) == _or_(y, x) 27.87/15.26 _xor_(x, y) == _xor_(y, x) 27.87/15.26 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.26 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.26 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.26 27.87/15.26 The set E# consists of the following equations: 27.87/15.26 27.87/15.26 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.26 _AND_(x, y) == _AND_(y, x) 27.87/15.26 27.87/15.26 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (32) PisEmptyProof (EQUIVALENT) 27.87/15.26 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (33) 27.87/15.26 YES 27.87/15.26 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (34) 27.87/15.26 Obligation: 27.87/15.26 The TRS P consists of the following rules: 27.87/15.26 27.87/15.26 _OR_(_or_(A, B), ext) -> _OR_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 27.87/15.26 The TRS R consists of the following rules: 27.87/15.26 27.87/15.26 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.26 U11(tt, A) -> A 27.87/15.26 U111(tt) -> false 27.87/15.26 U121(tt, A) -> A 27.87/15.26 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.26 U132(tt, U') -> U' 27.87/15.26 U141(tt, U) -> U 27.87/15.26 U151(tt, A) -> _xor_(A, true) 27.87/15.26 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.26 U31(tt) -> false 27.87/15.26 U41(tt, A) -> A 27.87/15.26 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.26 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.26 U62(tt) -> false 27.87/15.26 U71(tt) -> true 27.87/15.26 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.26 U91(tt) -> false 27.87/15.26 _and_(A, A) -> U11(isBool(A), A) 27.87/15.26 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.26 _and_(false, A) -> U31(isBool(A)) 27.87/15.26 _and_(true, A) -> U41(isBool(A), A) 27.87/15.26 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.26 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.26 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _xor_(A, A) -> U111(isBool(A)) 27.87/15.26 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.26 and(tt, X) -> X 27.87/15.26 equal(X, X) -> tt 27.87/15.26 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.26 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.26 isBool(false) -> tt 27.87/15.26 isBool(true) -> tt 27.87/15.26 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(not_(V1)) -> isBool(V1) 27.87/15.26 not_(A) -> U151(isBool(A), A) 27.87/15.26 not_(false) -> true 27.87/15.26 not_(true) -> false 27.87/15.26 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.26 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.26 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.26 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.26 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.26 27.87/15.26 The set E consists of the following equations: 27.87/15.26 27.87/15.26 _and_(x, y) == _and_(y, x) 27.87/15.26 _or_(x, y) == _or_(y, x) 27.87/15.26 _xor_(x, y) == _xor_(y, x) 27.87/15.26 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.26 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.26 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.26 27.87/15.26 The set E# consists of the following equations: 27.87/15.26 27.87/15.26 _AND_(x, y) == _AND_(y, x) 27.87/15.26 _OR_(x, y) == _OR_(y, x) 27.87/15.26 _XOR_(x, y) == _XOR_(y, x) 27.87/15.26 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.26 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.26 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.26 27.87/15.26 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (35) ESharpUsableEquationsProof (EQUIVALENT) 27.87/15.26 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 27.87/15.26 _AND_(x, y) == _AND_(y, x) 27.87/15.26 _XOR_(x, y) == _XOR_(y, x) 27.87/15.26 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.87/15.26 _XOR_(_xor_(x, y), z) == _XOR_(x, _xor_(y, z)) 27.87/15.26 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (36) 27.87/15.26 Obligation: 27.87/15.26 The TRS P consists of the following rules: 27.87/15.26 27.87/15.26 _OR_(_or_(A, B), ext) -> _OR_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 27.87/15.26 The TRS R consists of the following rules: 27.87/15.26 27.87/15.26 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.26 U11(tt, A) -> A 27.87/15.26 U111(tt) -> false 27.87/15.26 U121(tt, A) -> A 27.87/15.26 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.26 U132(tt, U') -> U' 27.87/15.26 U141(tt, U) -> U 27.87/15.26 U151(tt, A) -> _xor_(A, true) 27.87/15.26 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.26 U31(tt) -> false 27.87/15.26 U41(tt, A) -> A 27.87/15.26 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.26 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.26 U62(tt) -> false 27.87/15.26 U71(tt) -> true 27.87/15.26 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.26 U91(tt) -> false 27.87/15.26 _and_(A, A) -> U11(isBool(A), A) 27.87/15.26 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.26 _and_(false, A) -> U31(isBool(A)) 27.87/15.26 _and_(true, A) -> U41(isBool(A), A) 27.87/15.26 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.26 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.26 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _xor_(A, A) -> U111(isBool(A)) 27.87/15.26 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.26 and(tt, X) -> X 27.87/15.26 equal(X, X) -> tt 27.87/15.26 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.26 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.26 isBool(false) -> tt 27.87/15.26 isBool(true) -> tt 27.87/15.26 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(not_(V1)) -> isBool(V1) 27.87/15.26 not_(A) -> U151(isBool(A), A) 27.87/15.26 not_(false) -> true 27.87/15.26 not_(true) -> false 27.87/15.26 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.26 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.26 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.26 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.26 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.26 27.87/15.26 The set E consists of the following equations: 27.87/15.26 27.87/15.26 _and_(x, y) == _and_(y, x) 27.87/15.26 _or_(x, y) == _or_(y, x) 27.87/15.26 _xor_(x, y) == _xor_(y, x) 27.87/15.26 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.26 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.26 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.26 27.87/15.26 The set E# consists of the following equations: 27.87/15.26 27.87/15.26 _OR_(x, y) == _OR_(y, x) 27.87/15.26 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.26 27.87/15.26 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (37) EDPPoloProof (EQUIVALENT) 27.87/15.26 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 27.87/15.26 27.87/15.26 27.87/15.26 _OR_(_or_(A, B), ext) -> _OR_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 27.87/15.26 27.87/15.26 27.87/15.26 _and_(false, A) -> U31(isBool(A)) 27.87/15.26 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.26 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.26 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.26 _and_(A, A) -> U11(isBool(A), A) 27.87/15.26 _and_(true, A) -> U41(isBool(A), A) 27.87/15.26 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.26 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.26 _xor_(A, A) -> U111(isBool(A)) 27.87/15.26 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.26 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.26 U11(tt, A) -> A 27.87/15.26 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.26 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.26 U41(tt, A) -> A 27.87/15.26 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 U121(tt, A) -> A 27.87/15.26 U31(tt) -> false 27.87/15.26 U111(tt) -> false 27.87/15.26 We had to orient the following equations of E# equivalently. 27.87/15.26 27.87/15.26 27.87/15.26 _OR_(x, y) == _OR_(y, x) 27.87/15.26 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.26 With the implicit AFS we had to orient the following usable equations of E equivalently. 27.87/15.26 27.87/15.26 27.87/15.26 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.26 _and_(x, y) == _and_(y, x) 27.87/15.26 _xor_(x, y) == _xor_(y, x) 27.87/15.26 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.26 _or_(x, y) == _or_(y, x) 27.87/15.26 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.26 Used ordering: POLO with Polynomial interpretation [POLO]: 27.87/15.26 27.87/15.26 POL(U101(x_1, x_2, x_3)) = 2 + 3*x_2 + 2*x_2*x_3 + 3*x_3 27.87/15.26 POL(U11(x_1, x_2)) = 2*x_2 27.87/15.26 POL(U111(x_1)) = 0 27.87/15.26 POL(U121(x_1, x_2)) = x_2 27.87/15.26 POL(U21(x_1, x_2, x_3, x_4)) = 1 + 2*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + x_3 + x_4 27.87/15.26 POL(U31(x_1)) = 0 27.87/15.26 POL(U41(x_1, x_2)) = 2*x_2 27.87/15.26 POL(_OR_(x_1, x_2)) = 3*x_1 + 2*x_1*x_2 + 3*x_2 27.87/15.26 POL(_and_(x_1, x_2)) = x_1 + 2*x_1*x_2 + x_2 27.87/15.26 POL(_implies_(x_1, x_2)) = 0 27.87/15.26 POL(_isEqualTo_(x_1, x_2)) = 0 27.87/15.26 POL(_isNotEqualTo_(x_1, x_2)) = 0 27.87/15.26 POL(_or_(x_1, x_2)) = 3 + 3*x_1 + 2*x_1*x_2 + 3*x_2 27.87/15.26 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 27.87/15.26 POL(and(x_1, x_2)) = 0 27.87/15.26 POL(false) = 0 27.87/15.26 POL(isBool(x_1)) = 0 27.87/15.26 POL(isUniversal(x_1)) = 0 27.87/15.26 POL(not_(x_1)) = 0 27.87/15.26 POL(true) = 2 27.87/15.26 POL(tt) = 0 27.87/15.26 27.87/15.26 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (38) 27.87/15.26 Obligation: 27.87/15.26 P is empty. 27.87/15.26 The TRS R consists of the following rules: 27.87/15.26 27.87/15.26 U101(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.87/15.26 U11(tt, A) -> A 27.87/15.26 U111(tt) -> false 27.87/15.26 U121(tt, A) -> A 27.87/15.26 U131(tt, B, U') -> U132(equal(_isNotEqualTo_(B, true), true), U') 27.87/15.26 U132(tt, U') -> U' 27.87/15.26 U141(tt, U) -> U 27.87/15.26 U151(tt, A) -> _xor_(A, true) 27.87/15.26 U21(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.87/15.26 U31(tt) -> false 27.87/15.26 U41(tt, A) -> A 27.87/15.26 U51(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.87/15.26 U61(tt, U', U) -> U62(equal(_isNotEqualTo_(U, U'), true)) 27.87/15.26 U62(tt) -> false 27.87/15.26 U71(tt) -> true 27.87/15.26 U81(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.87/15.26 U91(tt) -> false 27.87/15.26 _and_(A, A) -> U11(isBool(A), A) 27.87/15.26 _and_(A, _xor_(B, C)) -> U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C) 27.87/15.26 _and_(false, A) -> U31(isBool(A)) 27.87/15.26 _and_(true, A) -> U41(isBool(A), A) 27.87/15.26 _implies_(A, B) -> U51(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _isEqualTo_(U, U') -> U61(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isEqualTo_(U, U) -> U71(isS(U)) 27.87/15.26 _isNotEqualTo_(U, U') -> U81(and(isS(U'), isS(U)), U', U) 27.87/15.26 _isNotEqualTo_(U, U) -> U91(isS(U)) 27.87/15.26 _or_(A, B) -> U101(and(isBool(A), isBool(B)), A, B) 27.87/15.26 _xor_(A, A) -> U111(isBool(A)) 27.87/15.26 _xor_(false, A) -> U121(isBool(A), A) 27.87/15.26 and(tt, X) -> X 27.87/15.26 equal(X, X) -> tt 27.87/15.26 if_then_else_fi(B, U, U') -> U131(and(isBool(B), and(isS(U'), isS(U))), B, U') 27.87/15.26 if_then_else_fi(true, U, U') -> U141(and(isS(U'), isS(U)), U) 27.87/15.26 isBool(false) -> tt 27.87/15.26 isBool(true) -> tt 27.87/15.26 isBool(_and_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_implies_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_isEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_isNotEqualTo_(V1, V2)) -> and(isUniversal(V1), isUniversal(V2)) 27.87/15.26 isBool(_or_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(_xor_(V1, V2)) -> and(isBool(V1), isBool(V2)) 27.87/15.26 isBool(not_(V1)) -> isBool(V1) 27.87/15.26 not_(A) -> U151(isBool(A), A) 27.87/15.26 not_(false) -> true 27.87/15.26 not_(true) -> false 27.87/15.26 _and_(_and_(A, A), ext) -> _and_(U11(isBool(A), A), ext) 27.87/15.26 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U21(and(isBool(A), and(isBool(B), isBool(C))), A, B, C), ext) 27.87/15.26 _and_(_and_(false, A), ext) -> _and_(U31(isBool(A)), ext) 27.87/15.26 _and_(_and_(true, A), ext) -> _and_(U41(isBool(A), A), ext) 27.87/15.26 _or_(_or_(A, B), ext) -> _or_(U101(and(isBool(A), isBool(B)), A, B), ext) 27.87/15.26 _xor_(_xor_(A, A), ext) -> _xor_(U111(isBool(A)), ext) 27.87/15.26 _xor_(_xor_(false, A), ext) -> _xor_(U121(isBool(A), A), ext) 27.87/15.26 27.87/15.26 The set E consists of the following equations: 27.87/15.26 27.87/15.26 _and_(x, y) == _and_(y, x) 27.87/15.26 _or_(x, y) == _or_(y, x) 27.87/15.26 _xor_(x, y) == _xor_(y, x) 27.87/15.26 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.87/15.26 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.87/15.26 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.87/15.26 27.87/15.26 The set E# consists of the following equations: 27.87/15.26 27.87/15.26 _OR_(x, y) == _OR_(y, x) 27.87/15.26 _OR_(_or_(x, y), z) == _OR_(x, _or_(y, z)) 27.87/15.26 27.87/15.26 We have to consider all minimal (P,E#,R,E)-chains 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (39) PisEmptyProof (EQUIVALENT) 27.87/15.26 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 27.87/15.26 ---------------------------------------- 27.87/15.26 27.87/15.26 (40) 27.87/15.26 YES 28.00/15.30 EOF