12.70/6.10 NO 12.70/6.12 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 12.70/6.12 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 12.70/6.12 12.70/6.12 12.70/6.12 Termination of the given ETRS could be disproven: 12.70/6.12 12.70/6.12 (0) ETRS 12.70/6.12 (1) RRRPoloETRSProof [EQUIVALENT, 220 ms] 12.70/6.12 (2) ETRS 12.70/6.12 (3) RRRPoloETRSProof [EQUIVALENT, 62 ms] 12.70/6.12 (4) ETRS 12.70/6.12 (5) RRRPoloETRSProof [EQUIVALENT, 56 ms] 12.70/6.12 (6) ETRS 12.70/6.12 (7) RRRPoloETRSProof [EQUIVALENT, 36 ms] 12.70/6.12 (8) ETRS 12.70/6.12 (9) RRRPoloETRSProof [EQUIVALENT, 32 ms] 12.70/6.12 (10) ETRS 12.70/6.12 (11) RRRPoloETRSProof [EQUIVALENT, 39 ms] 12.70/6.12 (12) ETRS 12.70/6.12 (13) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] 12.70/6.12 (14) EDP 12.70/6.12 (15) EDependencyGraphProof [EQUIVALENT, 0 ms] 12.70/6.12 (16) EDP 12.70/6.12 (17) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 12.70/6.12 (18) EDP 12.70/6.12 (19) EDPProblemToQDPProblemProof [EQUIVALENT, 4 ms] 12.70/6.12 (20) QDP 12.70/6.12 (21) TransformationProof [EQUIVALENT, 0 ms] 12.70/6.12 (22) QDP 12.70/6.12 (23) TransformationProof [EQUIVALENT, 0 ms] 12.70/6.12 (24) QDP 12.70/6.12 (25) NonTerminationLoopProof [COMPLETE, 0 ms] 12.70/6.12 (26) NO 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (0) 12.70/6.12 Obligation: 12.70/6.12 Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, A) -> A 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _and_(false, A) -> false 12.70/6.12 _and_(true, A) -> A 12.70/6.12 _implies_(A, B) -> not_(_xor_(A, _and_(A, B))) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 _xor_(A, A) -> false 12.70/6.12 _xor_(false, A) -> A 12.70/6.12 and(tt, X) -> X 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 not_(A) -> _xor_(A, true) 12.70/6.12 not_(false) -> true 12.70/6.12 not_(true) -> false 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (1) RRRPoloETRSProof (EQUIVALENT) 12.70/6.12 The following E TRS is given: Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, A) -> A 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _and_(false, A) -> false 12.70/6.12 _and_(true, A) -> A 12.70/6.12 _implies_(A, B) -> not_(_xor_(A, _and_(A, B))) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 _xor_(A, A) -> false 12.70/6.12 _xor_(false, A) -> A 12.70/6.12 and(tt, X) -> X 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 not_(A) -> _xor_(A, true) 12.70/6.12 not_(false) -> true 12.70/6.12 not_(true) -> false 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 12.70/6.12 12.70/6.12 _and_(A, A) -> A 12.70/6.12 _and_(false, A) -> false 12.70/6.12 _and_(true, A) -> A 12.70/6.12 _xor_(A, A) -> false 12.70/6.12 _xor_(false, A) -> A 12.70/6.12 not_(false) -> true 12.70/6.12 not_(true) -> false 12.70/6.12 Used ordering: 12.70/6.12 Polynomial interpretation [POLO]: 12.70/6.12 12.70/6.12 POL(U11(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 12.70/6.12 POL(U12(x_1)) = x_1 12.70/6.12 POL(U21(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 12.70/6.12 POL(U22(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_and_(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2 12.70/6.12 POL(_implies_(x_1, x_2)) = 3 + 3*x_1 + 3*x_1*x_2 + 3*x_2 12.70/6.12 POL(_isEqualTo_(x_1, x_2)) = x_1 + 2*x_2 12.70/6.12 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + 2*x_2 12.70/6.12 POL(_or_(x_1, x_2)) = 3 + 3*x_1 + 2*x_1*x_2 + 3*x_2 12.70/6.12 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 12.70/6.12 POL(and(x_1, x_2)) = 3*x_1 + 3*x_1*x_2 + 3*x_2 12.70/6.12 POL(equal(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(false) = 0 12.70/6.12 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 3*x_2 + 2*x_2*x_3 + 2*x_3 12.70/6.12 POL(not_(x_1)) = 1 + x_1 12.70/6.12 POL(true) = 0 12.70/6.12 POL(tt) = 0 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (2) 12.70/6.12 Obligation: 12.70/6.12 Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _implies_(A, B) -> not_(_xor_(A, _and_(A, B))) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 and(tt, X) -> X 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 not_(A) -> _xor_(A, true) 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (3) RRRPoloETRSProof (EQUIVALENT) 12.70/6.12 The following E TRS is given: Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _implies_(A, B) -> not_(_xor_(A, _and_(A, B))) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 and(tt, X) -> X 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 not_(A) -> _xor_(A, true) 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 12.70/6.12 12.70/6.12 not_(A) -> _xor_(A, true) 12.70/6.12 Used ordering: 12.70/6.12 Polynomial interpretation [POLO]: 12.70/6.12 12.70/6.12 POL(U11(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 12.70/6.12 POL(U12(x_1)) = x_1 12.70/6.12 POL(U21(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 12.70/6.12 POL(U22(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_and_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 12.70/6.12 POL(_implies_(x_1, x_2)) = 3 + 3*x_1 + x_1*x_2 + x_2 12.70/6.12 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_or_(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2 12.70/6.12 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 12.70/6.12 POL(and(x_1, x_2)) = 3*x_1 + 3*x_1*x_2 + 3*x_2 12.70/6.12 POL(equal(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(false) = 0 12.70/6.12 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 12.70/6.12 POL(not_(x_1)) = 2 + x_1 12.70/6.12 POL(true) = 0 12.70/6.12 POL(tt) = 0 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (4) 12.70/6.12 Obligation: 12.70/6.12 Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _implies_(A, B) -> not_(_xor_(A, _and_(A, B))) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 and(tt, X) -> X 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (5) RRRPoloETRSProof (EQUIVALENT) 12.70/6.12 The following E TRS is given: Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _implies_(A, B) -> not_(_xor_(A, _and_(A, B))) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 and(tt, X) -> X 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 12.70/6.12 12.70/6.12 _implies_(A, B) -> not_(_xor_(A, _and_(A, B))) 12.70/6.12 Used ordering: 12.70/6.12 Polynomial interpretation [POLO]: 12.70/6.12 12.70/6.12 POL(U11(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 12.70/6.12 POL(U12(x_1)) = x_1 12.70/6.12 POL(U21(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 12.70/6.12 POL(U22(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_and_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 12.70/6.12 POL(_implies_(x_1, x_2)) = 3 + 3*x_1 + x_1*x_2 + x_2 12.70/6.12 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_or_(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2 12.70/6.12 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 12.70/6.12 POL(and(x_1, x_2)) = 3*x_1 + 2*x_1*x_2 + x_2 12.70/6.12 POL(equal(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(false) = 0 12.70/6.12 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 12.70/6.12 POL(not_(x_1)) = 1 + x_1 12.70/6.12 POL(true) = 0 12.70/6.12 POL(tt) = 0 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (6) 12.70/6.12 Obligation: 12.70/6.12 Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 and(tt, X) -> X 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (7) RRRPoloETRSProof (EQUIVALENT) 12.70/6.12 The following E TRS is given: Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 and(tt, X) -> X 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 12.70/6.12 12.70/6.12 and(tt, X) -> X 12.70/6.12 Used ordering: 12.70/6.12 Polynomial interpretation [POLO]: 12.70/6.12 12.70/6.12 POL(U11(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 12.70/6.12 POL(U12(x_1)) = x_1 12.70/6.12 POL(U21(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 12.70/6.12 POL(U22(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_and_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 12.70/6.12 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_or_(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2 12.70/6.12 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 12.70/6.12 POL(and(x_1, x_2)) = 2 + 3*x_1 + 3*x_1*x_2 + 3*x_2 12.70/6.12 POL(equal(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(false) = 0 12.70/6.12 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 12.70/6.12 POL(true) = 0 12.70/6.12 POL(tt) = 0 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (8) 12.70/6.12 Obligation: 12.70/6.12 Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (9) RRRPoloETRSProof (EQUIVALENT) 12.70/6.12 The following E TRS is given: Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 12.70/6.12 12.70/6.12 _or_(A, B) -> _xor_(_and_(A, B), _xor_(A, B)) 12.70/6.12 Used ordering: 12.70/6.12 Polynomial interpretation [POLO]: 12.70/6.12 12.70/6.12 POL(U11(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 12.70/6.12 POL(U12(x_1)) = x_1 12.70/6.12 POL(U21(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 12.70/6.12 POL(U22(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_and_(x_1, x_2)) = x_1 + x_1*x_2 + x_2 12.70/6.12 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_or_(x_1, x_2)) = 3 + 3*x_1 + 2*x_1*x_2 + 3*x_2 12.70/6.12 POL(_xor_(x_1, x_2)) = 1 + x_1 + x_2 12.70/6.12 POL(equal(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(false) = 0 12.70/6.12 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 12.70/6.12 POL(true) = 0 12.70/6.12 POL(tt) = 0 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (10) 12.70/6.12 Obligation: 12.70/6.12 Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (11) RRRPoloETRSProof (EQUIVALENT) 12.70/6.12 The following E TRS is given: Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 The following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly by a polynomial ordering: 12.70/6.12 12.70/6.12 _and_(A, _xor_(B, C)) -> _xor_(_and_(A, B), _and_(A, C)) 12.70/6.12 Used ordering: 12.70/6.12 Polynomial interpretation [POLO]: 12.70/6.12 12.70/6.12 POL(U11(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 12.70/6.12 POL(U12(x_1)) = x_1 12.70/6.12 POL(U21(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 12.70/6.12 POL(U22(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_and_(x_1, x_2)) = 2 + 2*x_1 + x_1*x_2 + 2*x_2 12.70/6.12 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_or_(x_1, x_2)) = 1 + 2*x_1 + 2*x_1*x_2 + 2*x_2 12.70/6.12 POL(_xor_(x_1, x_2)) = 3 + x_1 + x_2 12.70/6.12 POL(equal(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(false) = 0 12.70/6.12 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 12.70/6.12 POL(true) = 0 12.70/6.12 POL(tt) = 0 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (12) 12.70/6.12 Obligation: 12.70/6.12 Equational rewrite system: 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (13) EquationalDependencyPairsProof (EQUIVALENT) 12.70/6.12 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 12.70/6.12 The TRS P consists of the following rules: 12.70/6.12 12.70/6.12 U11^1(tt, U', U) -> U12^1(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U11^1(tt, U', U) -> EQUAL(_isNotEqualTo_(U, U'), true) 12.70/6.12 U11^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 12.70/6.12 U21^1(tt, B, U') -> U22^1(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U21^1(tt, B, U') -> EQUAL(_isNotEqualTo_(B, true), true) 12.70/6.12 U21^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 12.70/6.12 _ISEQUALTO_(U, U') -> U11^1(tt, U', U) 12.70/6.12 _ISNOTEQUALTO_(U, U') -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 12.70/6.12 _ISNOTEQUALTO_(U, U') -> _ISEQUALTO_(U, U') 12.70/6.12 IF_THEN_ELSE_FI(B, U, U') -> U21^1(tt, B, U') 12.70/6.12 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 E# is empty. 12.70/6.12 We have to consider all minimal (P,E#,R,E)-chains 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (14) 12.70/6.12 Obligation: 12.70/6.12 The TRS P consists of the following rules: 12.70/6.12 12.70/6.12 U11^1(tt, U', U) -> U12^1(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U11^1(tt, U', U) -> EQUAL(_isNotEqualTo_(U, U'), true) 12.70/6.12 U11^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 12.70/6.12 U21^1(tt, B, U') -> U22^1(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U21^1(tt, B, U') -> EQUAL(_isNotEqualTo_(B, true), true) 12.70/6.12 U21^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 12.70/6.12 _ISEQUALTO_(U, U') -> U11^1(tt, U', U) 12.70/6.12 _ISNOTEQUALTO_(U, U') -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 12.70/6.12 _ISNOTEQUALTO_(U, U') -> _ISEQUALTO_(U, U') 12.70/6.12 IF_THEN_ELSE_FI(B, U, U') -> U21^1(tt, B, U') 12.70/6.12 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 E# is empty. 12.70/6.12 We have to consider all minimal (P,E#,R,E)-chains 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (15) EDependencyGraphProof (EQUIVALENT) 12.70/6.12 The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 4 less nodes. 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (16) 12.70/6.12 Obligation: 12.70/6.12 The TRS P consists of the following rules: 12.70/6.12 12.70/6.12 IF_THEN_ELSE_FI(B, U, U') -> U21^1(tt, B, U') 12.70/6.12 _ISEQUALTO_(U, U') -> U11^1(tt, U', U) 12.70/6.12 _ISNOTEQUALTO_(U, U') -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 12.70/6.12 U21^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 12.70/6.12 U11^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 12.70/6.12 _ISNOTEQUALTO_(U, U') -> _ISEQUALTO_(U, U') 12.70/6.12 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 The set E consists of the following equations: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 12.70/6.12 E# is empty. 12.70/6.12 We have to consider all minimal (P,E#,R,E)-chains 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (17) EUsableRulesReductionPairsProof (EQUIVALENT) 12.70/6.12 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. 12.70/6.12 12.70/6.12 No dependency pairs are removed. 12.70/6.12 12.70/6.12 No rules are removed from R. 12.70/6.12 12.70/6.12 The following equations are removed from E: 12.70/6.12 12.70/6.12 _and_(x, y) == _and_(y, x) 12.70/6.12 _or_(x, y) == _or_(y, x) 12.70/6.12 _xor_(x, y) == _xor_(y, x) 12.70/6.12 _and_(_and_(x, y), z) == _and_(x, _and_(y, z)) 12.70/6.12 _or_(_or_(x, y), z) == _or_(x, _or_(y, z)) 12.70/6.12 _xor_(_xor_(x, y), z) == _xor_(x, _xor_(y, z)) 12.70/6.12 Used ordering: POLO with Polynomial interpretation [POLO]: 12.70/6.12 12.70/6.12 POL(IF_THEN_ELSE_FI(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 12.70/6.12 POL(U11(x_1, x_2, x_3)) = 2*x_1 + x_2 + x_3 12.70/6.12 POL(U11^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 12.70/6.12 POL(U12(x_1)) = x_1 12.70/6.12 POL(U21(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 12.70/6.12 POL(U21^1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 12.70/6.12 POL(U22(x_1, x_2)) = x_1 + 2*x_2 12.70/6.12 POL(_ISEQUALTO_(x_1, x_2)) = 2*x_1 + 2*x_2 12.70/6.12 POL(_ISNOTEQUALTO_(x_1, x_2)) = 2*x_1 + 2*x_2 12.70/6.12 POL(_isEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(_isNotEqualTo_(x_1, x_2)) = x_1 + x_2 12.70/6.12 POL(equal(x_1, x_2)) = x_1 + 2*x_2 12.70/6.12 POL(false) = 0 12.70/6.12 POL(if_then_else_fi(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3 12.70/6.12 POL(true) = 0 12.70/6.12 POL(tt) = 0 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (18) 12.70/6.12 Obligation: 12.70/6.12 The TRS P consists of the following rules: 12.70/6.12 12.70/6.12 IF_THEN_ELSE_FI(B, U, U') -> U21^1(tt, B, U') 12.70/6.12 _ISEQUALTO_(U, U') -> U11^1(tt, U', U) 12.70/6.12 _ISNOTEQUALTO_(U, U') -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 12.70/6.12 U21^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 12.70/6.12 U11^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 12.70/6.12 _ISNOTEQUALTO_(U, U') -> _ISEQUALTO_(U, U') 12.70/6.12 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 E is empty. 12.70/6.12 E# is empty. 12.70/6.12 We have to consider all minimal (P,E#,R,E)-chains 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (19) EDPProblemToQDPProblemProof (EQUIVALENT) 12.70/6.12 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. 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (20) 12.70/6.12 Obligation: 12.70/6.12 Q DP problem: 12.70/6.12 The TRS P consists of the following rules: 12.70/6.12 12.70/6.12 IF_THEN_ELSE_FI(B, U, U') -> U21^1(tt, B, U') 12.70/6.12 _ISEQUALTO_(U, U') -> U11^1(tt, U', U) 12.70/6.12 _ISNOTEQUALTO_(U, U') -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 12.70/6.12 U21^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 12.70/6.12 U11^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 12.70/6.12 _ISNOTEQUALTO_(U, U') -> _ISEQUALTO_(U, U') 12.70/6.12 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 Q is empty. 12.70/6.12 We have to consider all minimal (P,Q,R)-chains. 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (21) TransformationProof (EQUIVALENT) 12.70/6.12 By instantiating [LPAR04] the rule IF_THEN_ELSE_FI(B, U, U') -> U21^1(tt, B, U') we obtained the following new rules [LPAR04]: 12.70/6.12 12.70/6.12 (IF_THEN_ELSE_FI(y_2, false, true) -> U21^1(tt, y_2, true),IF_THEN_ELSE_FI(y_2, false, true) -> U21^1(tt, y_2, true)) 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (22) 12.70/6.12 Obligation: 12.70/6.12 Q DP problem: 12.70/6.12 The TRS P consists of the following rules: 12.70/6.12 12.70/6.12 _ISEQUALTO_(U, U') -> U11^1(tt, U', U) 12.70/6.12 _ISNOTEQUALTO_(U, U') -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 12.70/6.12 U21^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) 12.70/6.12 U11^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 12.70/6.12 _ISNOTEQUALTO_(U, U') -> _ISEQUALTO_(U, U') 12.70/6.12 IF_THEN_ELSE_FI(y_2, false, true) -> U21^1(tt, y_2, true) 12.70/6.12 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 Q is empty. 12.70/6.12 We have to consider all minimal (P,Q,R)-chains. 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (23) TransformationProof (EQUIVALENT) 12.70/6.12 By instantiating [LPAR04] the rule U21^1(tt, B, U') -> _ISNOTEQUALTO_(B, true) we obtained the following new rules [LPAR04]: 12.70/6.12 12.70/6.12 (U21^1(tt, y_0, true) -> _ISNOTEQUALTO_(y_0, true),U21^1(tt, y_0, true) -> _ISNOTEQUALTO_(y_0, true)) 12.70/6.12 12.70/6.12 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (24) 12.70/6.12 Obligation: 12.70/6.12 Q DP problem: 12.70/6.12 The TRS P consists of the following rules: 12.70/6.12 12.70/6.12 _ISEQUALTO_(U, U') -> U11^1(tt, U', U) 12.70/6.12 _ISNOTEQUALTO_(U, U') -> IF_THEN_ELSE_FI(_isEqualTo_(U, U'), false, true) 12.70/6.12 U11^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 12.70/6.12 _ISNOTEQUALTO_(U, U') -> _ISEQUALTO_(U, U') 12.70/6.12 IF_THEN_ELSE_FI(y_2, false, true) -> U21^1(tt, y_2, true) 12.70/6.12 U21^1(tt, y_0, true) -> _ISNOTEQUALTO_(y_0, true) 12.70/6.12 12.70/6.12 The TRS R consists of the following rules: 12.70/6.12 12.70/6.12 U11(tt, U', U) -> U12(equal(_isNotEqualTo_(U, U'), true)) 12.70/6.12 U12(tt) -> false 12.70/6.12 U21(tt, B, U') -> U22(equal(_isNotEqualTo_(B, true), true), U') 12.70/6.12 U22(tt, U') -> U' 12.70/6.12 _isEqualTo_(U, U') -> U11(tt, U', U) 12.70/6.12 _isEqualTo_(U, U) -> true 12.70/6.12 _isNotEqualTo_(U, U') -> if_then_else_fi(_isEqualTo_(U, U'), false, true) 12.70/6.12 _isNotEqualTo_(U, U) -> false 12.70/6.12 equal(X, X) -> tt 12.70/6.12 if_then_else_fi(B, U, U') -> U21(tt, B, U') 12.70/6.12 if_then_else_fi(true, U, U') -> U 12.70/6.12 12.70/6.12 Q is empty. 12.70/6.12 We have to consider all minimal (P,Q,R)-chains. 12.70/6.12 ---------------------------------------- 12.70/6.12 12.70/6.12 (25) NonTerminationLoopProof (COMPLETE) 12.70/6.12 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 12.70/6.12 Found a loop by narrowing to the right: 12.70/6.12 12.70/6.12 s = _ISEQUALTO_(U, U') evaluates to t =_ISEQUALTO_(U, U') 12.70/6.12 12.70/6.12 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 12.70/6.12 * Matcher: [ ] 12.70/6.12 * Semiunifier: [ ] 12.70/6.12 12.70/6.12 -------------------------------------------------------------------------------- 12.70/6.13 Rewriting sequence 12.70/6.13 12.70/6.13 _ISEQUALTO_(U, U') -> U11^1(tt, U', U) 12.70/6.13 with rule _ISEQUALTO_(U, U') -> U11^1(tt, U', U) and matcher [ ]. 12.70/6.13 12.70/6.13 U11^1(tt, U', U) -> _ISNOTEQUALTO_(U, U') 12.70/6.13 with rule U11^1(tt, U'', U1) -> _ISNOTEQUALTO_(U1, U'') at position [] and matcher [U'' / U', U1 / U] 12.70/6.13 12.70/6.13 _ISNOTEQUALTO_(U, U') -> _ISEQUALTO_(U, U') 12.70/6.13 with rule _ISNOTEQUALTO_(U'', U''') -> _ISEQUALTO_(U'', U''') at position [] and matcher [U'' / U, U''' / U'] 12.70/6.13 12.70/6.13 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 12.70/6.13 12.70/6.13 12.70/6.13 All these steps are and every following step will be a correct step w.r.t to Q. 12.70/6.13 12.70/6.13 12.70/6.13 12.70/6.13 12.70/6.13 ---------------------------------------- 12.70/6.13 12.70/6.13 (26) 12.70/6.13 NO 12.89/6.16 EOF