27.56/14.61 NO 27.56/14.63 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 27.56/14.63 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 27.56/14.63 27.56/14.63 27.56/14.63 Termination of the given ETRS could be disproven: 27.56/14.63 27.56/14.63 (0) ETRS 27.56/14.63 (1) RRRPoloETRSProof [EQUIVALENT, 293 ms] 27.56/14.63 (2) ETRS 27.56/14.63 (3) RRRPoloETRSProof [EQUIVALENT, 132 ms] 27.56/14.63 (4) ETRS 27.56/14.63 (5) RRRPoloETRSProof [EQUIVALENT, 73 ms] 27.56/14.63 (6) ETRS 27.56/14.63 (7) RRRPoloETRSProof [EQUIVALENT, 85 ms] 27.56/14.63 (8) ETRS 27.56/14.63 (9) RRRPoloETRSProof [EQUIVALENT, 59 ms] 27.56/14.63 (10) ETRS 27.56/14.63 (11) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] 27.56/14.63 (12) EDP 27.56/14.63 (13) EDependencyGraphProof [EQUIVALENT, 0 ms] 27.56/14.63 (14) AND 27.56/14.63 (15) EDP 27.56/14.63 (16) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 27.56/14.63 (17) EDP 27.56/14.63 (18) EUsableRulesReductionPairsProof [EQUIVALENT, 1 ms] 27.56/14.63 (19) EDP 27.56/14.63 (20) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] 27.56/14.63 (21) QDP 27.56/14.63 (22) TransformationProof [EQUIVALENT, 0 ms] 27.56/14.63 (23) QDP 27.56/14.63 (24) TransformationProof [EQUIVALENT, 0 ms] 27.56/14.63 (25) QDP 27.56/14.63 (26) TransformationProof [EQUIVALENT, 0 ms] 27.56/14.63 (27) QDP 27.56/14.63 (28) TransformationProof [EQUIVALENT, 0 ms] 27.56/14.63 (29) QDP 27.56/14.63 (30) NonTerminationLoopProof [COMPLETE, 0 ms] 27.56/14.63 (31) NO 27.56/14.63 (32) EDP 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (0) 27.56/14.63 Obligation: 27.56/14.63 Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U21(tt, A, B) -> U22(tt, A, B) 27.56/14.63 U22(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U51(tt, A, B) -> U52(tt, A, B) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _implies_(A, B) -> U21(tt, A, B) 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _or_(A, B) -> U51(tt, A, B) 27.56/14.63 _xor_(A, A) -> false 27.56/14.63 _xor_(false, A) -> A 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 not_(A) -> _xor_(A, true) 27.56/14.63 not_(false) -> true 27.56/14.63 not_(true) -> false 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (1) RRRPoloETRSProof (EQUIVALENT) 27.56/14.63 The following E TRS is given: Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U21(tt, A, B) -> U22(tt, A, B) 27.56/14.63 U22(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U51(tt, A, B) -> U52(tt, A, B) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _implies_(A, B) -> U21(tt, A, B) 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _or_(A, B) -> U51(tt, A, B) 27.56/14.63 _xor_(A, A) -> false 27.56/14.63 _xor_(false, A) -> A 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 not_(A) -> _xor_(A, true) 27.56/14.63 not_(false) -> true 27.56/14.63 not_(true) -> false 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 27.56/14.63 27.56/14.63 U21(tt, A, B) -> U22(tt, A, B) 27.56/14.63 _xor_(A, A) -> false 27.56/14.63 _xor_(false, A) -> A 27.56/14.63 not_(false) -> true 27.56/14.63 not_(true) -> false 27.56/14.63 Used ordering: 27.56/14.63 Polynomial interpretation [POLO]: 27.56/14.63 27.56/14.63 POL(U11(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + 3*x_2*x_3 + 3*x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U12(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + 3*x_2*x_3 + 3*x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U13(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + 3*x_2*x_3 + 3*x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U21(x_1, x_2, x_3)) = 3 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 3*x_2 + 3*x_2*x_3 + 3*x_3 27.56/14.63 POL(U22(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + 3*x_2*x_3 + 2*x_3 27.56/14.63 POL(U31(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U32(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U33(x_1)) = x_1 27.56/14.63 POL(U41(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U42(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U51(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + 3*x_2*x_3 + 2*x_3 27.56/14.63 POL(U52(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + 3*x_2*x_3 + 2*x_3 27.56/14.63 POL(U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + 2*x_3 27.56/14.63 POL(U62(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + 2*x_3 27.56/14.63 POL(U63(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + 2*x_3 27.56/14.63 POL(U64(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(U71(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + x_2 27.56/14.63 POL(U72(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + x_2 27.56/14.63 POL(_and_(x_1, x_2)) = x_1 + 3*x_1*x_2 + x_2 27.56/14.63 POL(_implies_(x_1, x_2)) = 3 + 3*x_1 + 3*x_1*x_2 + 3*x_2 27.56/14.63 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(_or_(x_1, x_2)) = 2 + 3*x_1 + 3*x_1*x_2 + 3*x_2 27.56/14.63 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 27.56/14.63 POL(equal(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(false) = 0 27.56/14.63 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_1*x_2*x_3 + 2*x_2 + 2*x_2*x_3 + 2*x_3 27.56/14.63 POL(not_(x_1)) = 1 + x_1 27.56/14.63 POL(true) = 0 27.56/14.63 POL(tt) = 0 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (2) 27.56/14.63 Obligation: 27.56/14.63 Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U22(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U51(tt, A, B) -> U52(tt, A, B) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _implies_(A, B) -> U21(tt, A, B) 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _or_(A, B) -> U51(tt, A, B) 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 not_(A) -> _xor_(A, true) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (3) RRRPoloETRSProof (EQUIVALENT) 27.56/14.63 The following E TRS is given: Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U22(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U51(tt, A, B) -> U52(tt, A, B) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _implies_(A, B) -> U21(tt, A, B) 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _or_(A, B) -> U51(tt, A, B) 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 not_(A) -> _xor_(A, true) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 27.56/14.63 27.56/14.63 U22(tt, A, B) -> not_(_xor_(A, _and_(A, B))) 27.56/14.63 _implies_(A, B) -> U21(tt, A, B) 27.56/14.63 Used ordering: 27.56/14.63 Polynomial interpretation [POLO]: 27.56/14.63 27.56/14.63 POL(U11(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + x_2*x_3 + x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U12(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + x_2*x_3 + x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U13(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + x_2*x_3 + x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U21(x_1, x_2, x_3)) = 1 + 2*x_1 + 3*x_1*x_2 + 3*x_1*x_2*x_3 + 3*x_1*x_3 + 3*x_2 + 3*x_2*x_3 + 3*x_3 27.56/14.63 POL(U22(x_1, x_2, x_3)) = 3 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 3*x_2 + 2*x_2*x_3 + 2*x_3 27.56/14.63 POL(U31(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_3 27.56/14.63 POL(U32(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_3 27.56/14.63 POL(U33(x_1)) = x_1 27.56/14.63 POL(U41(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_3 27.56/14.63 POL(U42(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_3 27.56/14.63 POL(U51(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_2*x_3 + 2*x_3 27.56/14.63 POL(U52(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_2*x_3 + 2*x_3 27.56/14.63 POL(U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U62(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U63(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U64(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(U71(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + 2*x_2 27.56/14.63 POL(U72(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + 2*x_2 27.56/14.63 POL(_and_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 27.56/14.63 POL(_implies_(x_1, x_2)) = 2 + 3*x_1 + 3*x_1*x_2 + 3*x_2 27.56/14.63 POL(_isEqualTo_(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(_or_(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2 27.56/14.63 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 27.56/14.63 POL(equal(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(false) = 0 27.56/14.63 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(not_(x_1)) = 1 + x_1 27.56/14.63 POL(true) = 0 27.56/14.63 POL(tt) = 0 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (4) 27.56/14.63 Obligation: 27.56/14.63 Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U51(tt, A, B) -> U52(tt, A, B) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _or_(A, B) -> U51(tt, A, B) 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 not_(A) -> _xor_(A, true) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (5) RRRPoloETRSProof (EQUIVALENT) 27.56/14.63 The following E TRS is given: Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U51(tt, A, B) -> U52(tt, A, B) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _or_(A, B) -> U51(tt, A, B) 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 not_(A) -> _xor_(A, true) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 27.56/14.63 27.56/14.63 U51(tt, A, B) -> U52(tt, A, B) 27.56/14.63 not_(A) -> _xor_(A, true) 27.56/14.63 Used ordering: 27.56/14.63 Polynomial interpretation [POLO]: 27.56/14.63 27.56/14.63 POL(U11(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + x_2*x_3 + x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U12(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + x_2*x_3 + x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U13(x_1, x_2, x_3, x_4)) = 1 + 3*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + x_2*x_3 + x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U31(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_3 27.56/14.63 POL(U32(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_3 27.56/14.63 POL(U33(x_1)) = x_1 27.56/14.63 POL(U41(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_3 27.56/14.63 POL(U42(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_3 27.56/14.63 POL(U51(x_1, x_2, x_3)) = 3 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_2*x_3 + 2*x_3 27.56/14.63 POL(U52(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 2*x_2 + x_2*x_3 + 2*x_3 27.56/14.63 POL(U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U62(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U63(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U64(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(U71(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + x_2 27.56/14.63 POL(U72(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + x_2 27.56/14.63 POL(_and_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 27.56/14.63 POL(_isEqualTo_(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(_or_(x_1, x_2)) = 3 + 3*x_1 + 2*x_1*x_2 + 3*x_2 27.56/14.63 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 27.56/14.63 POL(equal(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(false) = 0 27.56/14.63 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 27.56/14.63 POL(not_(x_1)) = 2 + 3*x_1 + 3*x_1^2 27.56/14.63 POL(true) = 0 27.56/14.63 POL(tt) = 0 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (6) 27.56/14.63 Obligation: 27.56/14.63 Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _or_(A, B) -> U51(tt, A, B) 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (7) RRRPoloETRSProof (EQUIVALENT) 27.56/14.63 The following E TRS is given: Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _or_(A, B) -> U51(tt, A, B) 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 27.56/14.63 27.56/14.63 _or_(A, B) -> U51(tt, A, B) 27.56/14.63 Used ordering: 27.56/14.63 Polynomial interpretation [POLO]: 27.56/14.63 27.56/14.63 POL(U11(x_1, x_2, x_3, x_4)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 3*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U12(x_1, x_2, x_3, x_4)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 3*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U13(x_1, x_2, x_3, x_4)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + 2*x_2*x_3 + 2*x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U31(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U32(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U33(x_1)) = x_1 27.56/14.63 POL(U41(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U42(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U51(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U52(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 3*x_2 + 2*x_2*x_3 + 3*x_3 27.56/14.63 POL(U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + 2*x_3 27.56/14.63 POL(U62(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + 2*x_3 27.56/14.63 POL(U63(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + 2*x_3 27.56/14.63 POL(U64(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(U71(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + x_2 27.56/14.63 POL(U72(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + x_2 27.56/14.63 POL(_and_(x_1, x_2)) = x_1 + 2*x_1*x_2 + x_2 27.56/14.63 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(_or_(x_1, x_2)) = 1 + x_1 + x_2 27.56/14.63 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 27.56/14.63 POL(equal(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(false) = 0 27.56/14.63 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(true) = 0 27.56/14.63 POL(tt) = 0 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (8) 27.56/14.63 Obligation: 27.56/14.63 Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (9) RRRPoloETRSProof (EQUIVALENT) 27.56/14.63 The following E TRS is given: Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 27.56/14.63 27.56/14.63 U52(tt, A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 27.56/14.63 Used ordering: 27.56/14.63 Polynomial interpretation [POLO]: 27.56/14.63 27.56/14.63 POL(U11(x_1, x_2, x_3, x_4)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + 3*x_2*x_3 + 3*x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U12(x_1, x_2, x_3, x_4)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + 3*x_2*x_3 + 3*x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U13(x_1, x_2, x_3, x_4)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 3*x_1*x_2*x_3*x_4 + 2*x_1*x_2*x_4 + 2*x_1*x_3 + 3*x_1*x_3*x_4 + 2*x_1*x_4 + 2*x_2 + 3*x_2*x_3 + 3*x_2*x_4 + x_3 + x_4 27.56/14.63 POL(U31(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U32(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U33(x_1)) = x_1 27.56/14.63 POL(U41(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U42(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + x_3 27.56/14.63 POL(U52(x_1, x_2, x_3)) = 3 + 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + 3*x_2 + 3*x_2*x_3 + 3*x_3 27.56/14.63 POL(U61(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + 2*x_3 27.56/14.63 POL(U62(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + 2*x_3 27.56/14.63 POL(U63(x_1, x_2, x_3)) = 2*x_1 + 2*x_1*x_2 + 2*x_1*x_2*x_3 + 2*x_1*x_3 + x_2 + 2*x_3 27.56/14.63 POL(U64(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(U71(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + 2*x_2 27.56/14.63 POL(U72(x_1, x_2)) = 2*x_1 + 2*x_1*x_2 + x_2 27.56/14.63 POL(_and_(x_1, x_2)) = x_1 + 3*x_1*x_2 + x_2 27.56/14.63 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(_or_(x_1, x_2)) = 3 + 3*x_1 + 2*x_1*x_2 + 3*x_2 27.56/14.63 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 27.56/14.63 POL(equal(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(false) = 0 27.56/14.63 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(true) = 0 27.56/14.63 POL(tt) = 0 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (10) 27.56/14.63 Obligation: 27.56/14.63 Equational rewrite system: 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (11) EquationalDependencyPairsProof (EQUIVALENT) 27.56/14.63 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U11^1(tt, A, B, C) -> U12^1(tt, A, B, C) 27.56/14.63 U12^1(tt, A, B, C) -> U13^1(tt, A, B, C) 27.56/14.63 U13^1(tt, A, B, C) -> _AND_(A, B) 27.56/14.63 U13^1(tt, A, B, C) -> _AND_(A, C) 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 U32^1(tt, U', U) -> U33^1(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U32^1(tt, U', U) -> EQUAL(_isNotEqualTo_(U, U'), true) 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 U61^1(tt, B, U') -> U62^1(tt, B, U') 27.56/14.63 U62^1(tt, B, U') -> U63^1(tt, B, U') 27.56/14.63 U63^1(tt, B, U') -> U64^1(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U63^1(tt, B, U') -> EQUAL(_isNotEqualTo_(B, true), true) 27.56/14.63 U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.56/14.63 U71^1(tt, U) -> U72^1(tt, U) 27.56/14.63 _AND_(A, _xor_(B, C)) -> U11^1(tt, A, B, C) 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 IF_THEN_ELSE_FI(B, U, U') -> U61^1(tt, B, U') 27.56/14.63 IF_THEN_ELSE_FI(true, U, U') -> U71^1(tt, U) 27.56/14.63 _AND_(_and_(A, A), ext) -> _AND_(A, ext) 27.56/14.63 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U11(tt, A, B, C), ext) 27.56/14.63 _AND_(_and_(A, _xor_(B, C)), ext) -> U11^1(tt, A, B, C) 27.56/14.63 _AND_(_and_(false, A), ext) -> _AND_(false, ext) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 _and_(_and_(A, A), ext) -> _and_(A, ext) 27.56/14.63 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U11(tt, A, B, C), ext) 27.56/14.63 _and_(_and_(false, A), ext) -> _and_(false, ext) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 The set E# consists of the following equations: 27.56/14.63 27.56/14.63 _AND_(x, y) == _AND_(y, x) 27.56/14.63 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.56/14.63 27.56/14.63 We have to consider all minimal (P,E#,R,E)-chains 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (12) 27.56/14.63 Obligation: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U11^1(tt, A, B, C) -> U12^1(tt, A, B, C) 27.56/14.63 U12^1(tt, A, B, C) -> U13^1(tt, A, B, C) 27.56/14.63 U13^1(tt, A, B, C) -> _AND_(A, B) 27.56/14.63 U13^1(tt, A, B, C) -> _AND_(A, C) 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 U32^1(tt, U', U) -> U33^1(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U32^1(tt, U', U) -> EQUAL(_isNotEqualTo_(U, U'), true) 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 U61^1(tt, B, U') -> U62^1(tt, B, U') 27.56/14.63 U62^1(tt, B, U') -> U63^1(tt, B, U') 27.56/14.63 U63^1(tt, B, U') -> U64^1(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U63^1(tt, B, U') -> EQUAL(_isNotEqualTo_(B, true), true) 27.56/14.63 U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.56/14.63 U71^1(tt, U) -> U72^1(tt, U) 27.56/14.63 _AND_(A, _xor_(B, C)) -> U11^1(tt, A, B, C) 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 IF_THEN_ELSE_FI(B, U, U') -> U61^1(tt, B, U') 27.56/14.63 IF_THEN_ELSE_FI(true, U, U') -> U71^1(tt, U) 27.56/14.63 _AND_(_and_(A, A), ext) -> _AND_(A, ext) 27.56/14.63 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U11(tt, A, B, C), ext) 27.56/14.63 _AND_(_and_(A, _xor_(B, C)), ext) -> U11^1(tt, A, B, C) 27.56/14.63 _AND_(_and_(false, A), ext) -> _AND_(false, ext) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 _and_(_and_(A, A), ext) -> _and_(A, ext) 27.56/14.63 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U11(tt, A, B, C), ext) 27.56/14.63 _and_(_and_(false, A), ext) -> _and_(false, ext) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 The set E# consists of the following equations: 27.56/14.63 27.56/14.63 _AND_(x, y) == _AND_(y, x) 27.56/14.63 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.56/14.63 27.56/14.63 We have to consider all minimal (P,E#,R,E)-chains 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (13) EDependencyGraphProof (EQUIVALENT) 27.56/14.63 The approximation of the Equational Dependency Graph [DA_STEIN] contains 2 SCCs with 6 less nodes. 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (14) 27.56/14.63 Complex Obligation (AND) 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (15) 27.56/14.63 Obligation: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 U61^1(tt, B, U') -> U62^1(tt, B, U') 27.56/14.63 IF_THEN_ELSE_FI(B, U, U') -> U61^1(tt, B, U') 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 U62^1(tt, B, U') -> U63^1(tt, B, U') 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 _and_(_and_(A, A), ext) -> _and_(A, ext) 27.56/14.63 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U11(tt, A, B, C), ext) 27.56/14.63 _and_(_and_(false, A), ext) -> _and_(false, ext) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 The set E# consists of the following equations: 27.56/14.63 27.56/14.63 _AND_(x, y) == _AND_(y, x) 27.56/14.63 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.56/14.63 27.56/14.63 We have to consider all minimal (P,E#,R,E)-chains 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (16) ESharpUsableEquationsProof (EQUIVALENT) 27.56/14.63 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 27.56/14.63 _AND_(x, y) == _AND_(y, x) 27.56/14.63 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (17) 27.56/14.63 Obligation: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 U61^1(tt, B, U') -> U62^1(tt, B, U') 27.56/14.63 IF_THEN_ELSE_FI(B, U, U') -> U61^1(tt, B, U') 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 U62^1(tt, B, U') -> U63^1(tt, B, U') 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 _and_(_and_(A, A), ext) -> _and_(A, ext) 27.56/14.63 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U11(tt, A, B, C), ext) 27.56/14.63 _and_(_and_(false, A), ext) -> _and_(false, ext) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 E# is empty. 27.56/14.63 We have to consider all minimal (P,E#,R,E)-chains 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (18) EUsableRulesReductionPairsProof (EQUIVALENT) 27.56/14.63 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.56/14.63 27.56/14.63 No dependency pairs are removed. 27.56/14.63 27.56/14.63 The following rules are removed from R: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _and_(_and_(A, A), ext) -> _and_(A, ext) 27.56/14.63 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U11(tt, A, B, C), ext) 27.56/14.63 _and_(_and_(false, A), ext) -> _and_(false, ext) 27.56/14.63 The following equations are removed from E: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 Used ordering: POLO with Polynomial interpretation [POLO]: 27.56/14.63 27.56/14.63 POL(IF_THEN_ELSE_FI(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(U31(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 27.56/14.63 POL(U31^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(U32(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 27.56/14.63 POL(U32^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(U33(x_1)) = x_1 27.56/14.63 POL(U41(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 27.56/14.63 POL(U41^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(U42(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 27.56/14.63 POL(U42^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(U61(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 27.56/14.63 POL(U61^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(U62(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 27.56/14.63 POL(U62^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(U63(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 27.56/14.63 POL(U63^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(U64(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(U71(x_1, x_2)) = 2*x_1 + 2*x_2 27.56/14.63 POL(U72(x_1, x_2)) = 2*x_1 + 2*x_2 27.56/14.63 POL(_ISEQUALTO_(x_1, x_2)) = 2*x_1 + 2*x_2 27.56/14.63 POL(_ISNOTEQUALTO_(x_1, x_2)) = 2*x_1 + 2*x_2 27.56/14.63 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 27.56/14.63 POL(equal(x_1, x_2)) = x_1 + 2*x_2 27.56/14.63 POL(false) = 0 27.56/14.63 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 27.56/14.63 POL(true) = 0 27.56/14.63 POL(tt) = 0 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (19) 27.56/14.63 Obligation: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 U61^1(tt, B, U') -> U62^1(tt, B, U') 27.56/14.63 IF_THEN_ELSE_FI(B, U, U') -> U61^1(tt, B, U') 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 U62^1(tt, B, U') -> U63^1(tt, B, U') 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U33(tt) -> false 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 equal(X, X) -> tt 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 27.56/14.63 E is empty. 27.56/14.63 E# is empty. 27.56/14.63 We have to consider all minimal (P,E#,R,E)-chains 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (20) EDPProblemToQDPProblemProof (EQUIVALENT) 27.56/14.63 The EDP problem does not contain equations anymore, so we can transform it with the EDP to QDP problem processor [DA_STEIN] into a QDP problem. 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (21) 27.56/14.63 Obligation: 27.56/14.63 Q DP problem: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 U61^1(tt, B, U') -> U62^1(tt, B, U') 27.56/14.63 IF_THEN_ELSE_FI(B, U, U') -> U61^1(tt, B, U') 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 U62^1(tt, B, U') -> U63^1(tt, B, U') 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U33(tt) -> false 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 equal(X, X) -> tt 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 27.56/14.63 Q is empty. 27.56/14.63 We have to consider all minimal (P,Q,R)-chains. 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (22) TransformationProof (EQUIVALENT) 27.56/14.63 By instantiating [LPAR04] the rule IF_THEN_ELSE_FI(B, U, U') -> U61^1(tt, B, U') we obtained the following new rules [LPAR04]: 27.56/14.63 27.56/14.63 (IF_THEN_ELSE_FI(y_2, false, true) -> U61^1(tt, y_2, true),IF_THEN_ELSE_FI(y_2, false, true) -> U61^1(tt, y_2, true)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (23) 27.56/14.63 Obligation: 27.56/14.63 Q DP problem: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 U61^1(tt, B, U') -> U62^1(tt, B, U') 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 U62^1(tt, B, U') -> U63^1(tt, B, U') 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 IF_THEN_ELSE_FI(y_2, false, true) -> U61^1(tt, y_2, true) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U33(tt) -> false 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 equal(X, X) -> tt 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 27.56/14.63 Q is empty. 27.56/14.63 We have to consider all minimal (P,Q,R)-chains. 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (24) TransformationProof (EQUIVALENT) 27.56/14.63 By instantiating [LPAR04] the rule U61^1(tt, B, U') -> U62^1(tt, B, U') we obtained the following new rules [LPAR04]: 27.56/14.63 27.56/14.63 (U61^1(tt, y_0, true) -> U62^1(tt, y_0, true),U61^1(tt, y_0, true) -> U62^1(tt, y_0, true)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (25) 27.56/14.63 Obligation: 27.56/14.63 Q DP problem: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 U62^1(tt, B, U') -> U63^1(tt, B, U') 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 IF_THEN_ELSE_FI(y_2, false, true) -> U61^1(tt, y_2, true) 27.56/14.63 U61^1(tt, y_0, true) -> U62^1(tt, y_0, true) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U33(tt) -> false 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 equal(X, X) -> tt 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 27.56/14.63 Q is empty. 27.56/14.63 We have to consider all minimal (P,Q,R)-chains. 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (26) TransformationProof (EQUIVALENT) 27.56/14.63 By instantiating [LPAR04] the rule U62^1(tt, B, U') -> U63^1(tt, B, U') we obtained the following new rules [LPAR04]: 27.56/14.63 27.56/14.63 (U62^1(tt, y_0, true) -> U63^1(tt, y_0, true),U62^1(tt, y_0, true) -> U63^1(tt, y_0, true)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (27) 27.56/14.63 Obligation: 27.56/14.63 Q DP problem: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 IF_THEN_ELSE_FI(y_2, false, true) -> U61^1(tt, y_2, true) 27.56/14.63 U61^1(tt, y_0, true) -> U62^1(tt, y_0, true) 27.56/14.63 U62^1(tt, y_0, true) -> U63^1(tt, y_0, true) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U33(tt) -> false 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 equal(X, X) -> tt 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 27.56/14.63 Q is empty. 27.56/14.63 We have to consider all minimal (P,Q,R)-chains. 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (28) TransformationProof (EQUIVALENT) 27.56/14.63 By instantiating [LPAR04] the rule U63^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) we obtained the following new rules [LPAR04]: 27.56/14.63 27.56/14.63 (U63^1(tt, y_0, true) -> _ISNOTEQUALTO_(y_0, true),U63^1(tt, y_0, true) -> _ISNOTEQUALTO_(y_0, true)) 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (29) 27.56/14.63 Obligation: 27.56/14.63 Q DP problem: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 27.56/14.63 U31^1(tt, U', U) -> U32^1(tt, U', U) 27.56/14.63 _ISNOTEQUALTO_(U, U') -> U41^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> _ISEQUALTO_(U, U') 27.56/14.63 _ISEQUALTO_(U, U') -> U31^1(tt, U', U) 27.56/14.63 U41^1(tt, U', U) -> U42^1(tt, U', U) 27.56/14.63 U42^1(tt, U', U) -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 27.56/14.63 IF_THEN_ELSE_FI(y_2, false, true) -> U61^1(tt, y_2, true) 27.56/14.63 U61^1(tt, y_0, true) -> U62^1(tt, y_0, true) 27.56/14.63 U62^1(tt, y_0, true) -> U63^1(tt, y_0, true) 27.56/14.63 U63^1(tt, y_0, true) -> _ISNOTEQUALTO_(y_0, true) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U33(tt) -> false 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 equal(X, X) -> tt 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 27.56/14.63 Q is empty. 27.56/14.63 We have to consider all minimal (P,Q,R)-chains. 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (30) NonTerminationLoopProof (COMPLETE) 27.56/14.63 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 27.56/14.63 Found a loop by narrowing to the right: 27.56/14.63 27.56/14.63 s = U32^1(tt, U'', U1) evaluates to t =U32^1(tt, U'', U1) 27.56/14.63 27.56/14.63 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 27.56/14.63 * Matcher: [ ] 27.56/14.63 * Semiunifier: [ ] 27.56/14.63 27.56/14.63 -------------------------------------------------------------------------------- 27.56/14.63 Rewriting sequence 27.56/14.63 27.56/14.63 U32^1(tt, U'', U1) -> _ISNOTEQUALTO_(U1, U'') 27.56/14.63 with rule U32^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') and matcher [U' / U'', U / U1]. 27.56/14.63 27.56/14.63 _ISNOTEQUALTO_(U1, U'') -> U41^1(tt, U'', U1) 27.56/14.63 with rule _ISNOTEQUALTO_(U''', U'''') -> U41^1(tt, U'''', U''') at position [] and matcher [U''' / U1, U'''' / U''] 27.56/14.63 27.56/14.63 U41^1(tt, U'', U1) -> U42^1(tt, U'', U1) 27.56/14.63 with rule U41^1(tt, U', U) -> U42^1(tt, U', U) at position [] and matcher [U' / U'', U / U1] 27.56/14.63 27.56/14.63 U42^1(tt, U'', U1) -> _ISEQUALTO_(U1, U'') 27.56/14.63 with rule U42^1(tt, U''', U1') -> _ISEQUALTO_(U1', U''') at position [] and matcher [U''' / U'', U1' / U1] 27.56/14.63 27.56/14.63 _ISEQUALTO_(U1, U'') -> U31^1(tt, U'', U1) 27.56/14.63 with rule _ISEQUALTO_(U, U') -> U31^1(tt, U', U) at position [] and matcher [U / U1, U' / U''] 27.56/14.63 27.56/14.63 U31^1(tt, U'', U1) -> U32^1(tt, U'', U1) 27.56/14.63 with rule U31^1(tt, U''', U1') -> U32^1(tt, U''', U1') at position [] and matcher [U''' / U'', U1' / U1] 27.56/14.63 27.56/14.63 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 27.56/14.63 27.56/14.63 27.56/14.63 All these steps are and every following step will be a correct step w.r.t to Q. 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (31) 27.56/14.63 NO 27.56/14.63 27.56/14.63 ---------------------------------------- 27.56/14.63 27.56/14.63 (32) 27.56/14.63 Obligation: 27.56/14.63 The TRS P consists of the following rules: 27.56/14.63 27.56/14.63 U13^1(tt, A, B, C) -> _AND_(A, B) 27.56/14.63 _AND_(_and_(A, _xor_(B, C)), ext) -> U11^1(tt, A, B, C) 27.56/14.63 _AND_(_and_(A, A), ext) -> _AND_(A, ext) 27.56/14.63 U12^1(tt, A, B, C) -> U13^1(tt, A, B, C) 27.56/14.63 _AND_(A, _xor_(B, C)) -> U11^1(tt, A, B, C) 27.56/14.63 U11^1(tt, A, B, C) -> U12^1(tt, A, B, C) 27.56/14.63 _AND_(_and_(A, _xor_(B, C)), ext) -> _AND_(U11(tt, A, B, C), ext) 27.56/14.63 _AND_(_and_(false, A), ext) -> _AND_(false, ext) 27.56/14.63 U13^1(tt, A, B, C) -> _AND_(A, C) 27.56/14.63 27.56/14.63 The TRS R consists of the following rules: 27.56/14.63 27.56/14.63 U11(tt, A, B, C) -> U12(tt, A, B, C) 27.56/14.63 U12(tt, A, B, C) -> U13(tt, A, B, C) 27.56/14.63 U13(tt, A, B, C) -> _xor_(_and_(A, B), _and_(A, C)) 27.56/14.63 U31(tt, U', U) -> U32(tt, U', U) 27.56/14.63 U32(tt, U', U) -> U33(equal(_isNotEqualTo_(U, U'), true)) 27.56/14.63 U33(tt) -> false 27.56/14.63 U41(tt, U', U) -> U42(tt, U', U) 27.56/14.63 U42(tt, U', U) -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 27.56/14.63 U61(tt, B, U') -> U62(tt, B, U') 27.56/14.63 U62(tt, B, U') -> U63(tt, B, U') 27.56/14.63 U63(tt, B, U') -> U64(equal(_isNotEqualTo_(B, true), true), U') 27.56/14.63 U64(tt, U') -> U' 27.56/14.63 U71(tt, U) -> U72(tt, U) 27.56/14.63 U72(tt, U) -> U 27.56/14.63 _and_(A, A) -> A 27.56/14.63 _and_(A, _xor_(B, C)) -> U11(tt, A, B, C) 27.56/14.63 _and_(false, A) -> false 27.56/14.63 _and_(true, A) -> A 27.56/14.63 _isEqualTo_(U, U') -> U31(tt, U', U) 27.56/14.63 _isEqualTo_(U, U) -> true 27.56/14.63 _isNotEqualTo_(U, U') -> U41(tt, U', U) 27.56/14.63 _isNotEqualTo_(U, U) -> false 27.56/14.63 equal(X, X) -> tt 27.56/14.63 if_then_else_fi(B, U, U') -> U61(tt, B, U') 27.56/14.63 if_then_else_fi(true, U, U') -> U71(tt, U) 27.56/14.63 _and_(_and_(A, A), ext) -> _and_(A, ext) 27.56/14.63 _and_(_and_(A, _xor_(B, C)), ext) -> _and_(U11(tt, A, B, C), ext) 27.56/14.63 _and_(_and_(false, A), ext) -> _and_(false, ext) 27.56/14.63 27.56/14.63 The set E consists of the following equations: 27.56/14.63 27.56/14.63 _and_(x, y) == _and_(y, x) 27.56/14.63 _or_(x, y) == _or_(y, x) 27.56/14.63 _xor_(x, y) == _xor_(y, x) 27.56/14.63 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 27.56/14.63 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 27.56/14.63 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 27.56/14.63 27.56/14.63 The set E# consists of the following equations: 27.56/14.63 27.56/14.63 _AND_(x, y) == _AND_(y, x) 27.56/14.63 _AND_(_and_(x, y), z) == _AND_(x, _and_(y, z)) 27.56/14.63 27.56/14.63 We have to consider all minimal (P,E#,R,E)-chains 27.85/14.66 EOF