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