23.76/14.39 YES 23.76/14.40 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 23.76/14.40 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 23.76/14.40 23.76/14.40 23.76/14.40 Termination of the given ETRS could be proven: 23.76/14.40 23.76/14.40 (0) ETRS 23.76/14.40 (1) EquationalDependencyPairsProof [EQUIVALENT, 200 ms] 23.76/14.40 (2) EDP 23.76/14.40 (3) EDependencyGraphProof [EQUIVALENT, 0 ms] 23.76/14.40 (4) AND 23.76/14.40 (5) EDP 23.76/14.40 (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 23.76/14.40 (7) EDP 23.76/14.40 (8) EUsableRulesReductionPairsProof [EQUIVALENT, 55 ms] 23.76/14.40 (9) EDP 23.76/14.40 (10) ERuleRemovalProof [EQUIVALENT, 7 ms] 23.76/14.40 (11) EDP 23.76/14.40 (12) PisEmptyProof [EQUIVALENT, 0 ms] 23.76/14.40 (13) YES 23.76/14.40 (14) EDP 23.76/14.40 (15) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 23.76/14.40 (16) EDP 23.76/14.40 (17) EDPPoloProof [EQUIVALENT, 3631 ms] 23.76/14.40 (18) EDP 23.76/14.40 (19) PisEmptyProof [EQUIVALENT, 0 ms] 23.76/14.40 (20) YES 23.76/14.40 (21) EDP 23.76/14.40 (22) ESharpUsableEquationsProof [EQUIVALENT, 5 ms] 23.76/14.40 (23) EDP 23.76/14.40 (24) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 23.76/14.40 (25) EDP 23.76/14.40 (26) PisEmptyProof [EQUIVALENT, 0 ms] 23.76/14.40 (27) YES 23.76/14.40 (28) EDP 23.76/14.40 (29) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 23.76/14.40 (30) EDP 23.76/14.40 (31) EUsableRulesReductionPairsProof [EQUIVALENT, 9 ms] 23.76/14.40 (32) EDP 23.76/14.40 (33) PisEmptyProof [EQUIVALENT, 0 ms] 23.76/14.40 (34) YES 23.76/14.40 (35) EDP 23.76/14.40 (36) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 23.76/14.40 (37) EDP 23.76/14.40 (38) EDPPoloProof [EQUIVALENT, 0 ms] 23.76/14.40 (39) EDP 23.76/14.40 (40) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 23.76/14.40 (41) EDP 23.76/14.40 (42) PisEmptyProof [EQUIVALENT, 0 ms] 23.76/14.40 (43) YES 23.76/14.40 (44) EDP 23.76/14.40 (45) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] 23.76/14.40 (46) EDP 23.76/14.40 (47) EDPPoloProof [EQUIVALENT, 0 ms] 23.76/14.40 (48) EDP 23.76/14.40 (49) PisEmptyProof [EQUIVALENT, 0 ms] 23.76/14.40 (50) YES 23.76/14.40 23.76/14.40 23.76/14.40 ---------------------------------------- 23.76/14.40 23.76/14.40 (0) 23.76/14.40 Obligation: 23.76/14.40 Equational rewrite system: 23.76/14.40 The TRS R consists of the following rules: 23.76/14.40 23.76/14.40 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.40 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.40 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.40 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.40 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.40 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.40 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.40 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.40 substt(x, id) -> x 23.76/14.40 substf(f, id) -> f 23.76/14.40 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.40 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.40 substt(1, .(x, s)) -> x 23.76/14.40 ron(id, s) -> s 23.76/14.40 ron(shift, .(x, s)) -> s 23.76/14.40 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.40 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.40 ron(s, id) -> s 23.76/14.40 .(1, shift) -> id 23.76/14.40 .(substt(1, s), ron(shift, s)) -> s 23.76/14.40 virg(emptyfset, a) -> a 23.76/14.40 virg(a, a) -> a 23.76/14.40 *(emptysset, a) -> a 23.76/14.40 *(a, a) -> a 23.76/14.40 neg(neg(f)) -> f 23.76/14.40 and(f, f) -> f 23.76/14.40 or(f, f) -> f 23.76/14.40 imp(f, g) -> or(neg(f), g) 23.76/14.40 exists(f) -> neg(forall(neg(f))) 23.76/14.40 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.40 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.40 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.40 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.40 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.40 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.40 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.40 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.40 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.40 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.40 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.40 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.40 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.40 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.40 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.40 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.40 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.40 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.40 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.40 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.40 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.40 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.40 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.40 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.40 23.76/14.40 The set E consists of the following equations: 23.76/14.40 23.76/14.40 *(x, y) == *(y, x) 23.76/14.40 virg(x, y) == virg(y, x) 23.76/14.40 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.40 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.40 23.76/14.40 23.76/14.40 ---------------------------------------- 23.76/14.40 23.76/14.40 (1) EquationalDependencyPairsProof (EQUIVALENT) 23.76/14.40 Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: 23.76/14.40 The TRS P consists of the following rules: 23.76/14.40 23.76/14.40 SUBSTT(ef(x), y) -> SUBSTT(x, y) 23.76/14.40 SUBSTF(Pe(x), y) -> SUBSTT(x, y) 23.76/14.40 SUBSTF(neg(f), s) -> NEG(substf(f, s)) 23.76/14.40 SUBSTF(neg(f), s) -> SUBSTF(f, s) 23.76/14.40 SUBSTF(and(f, g), s) -> AND(substf(f, s), substf(g, s)) 23.76/14.40 SUBSTF(and(f, g), s) -> SUBSTF(f, s) 23.76/14.40 SUBSTF(and(f, g), s) -> SUBSTF(g, s) 23.76/14.40 SUBSTF(or(f, g), s) -> OR(substf(f, s), substf(g, s)) 23.76/14.40 SUBSTF(or(f, g), s) -> SUBSTF(f, s) 23.76/14.40 SUBSTF(or(f, g), s) -> SUBSTF(g, s) 23.76/14.40 SUBSTF(imp(f, g), s) -> IMP(substf(f, s), substf(g, s)) 23.76/14.40 SUBSTF(imp(f, g), s) -> SUBSTF(f, s) 23.76/14.40 SUBSTF(imp(f, g), s) -> SUBSTF(g, s) 23.76/14.40 SUBSTF(forall(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.40 SUBSTF(forall(f), s) -> .^1(1, ron(s, shift)) 23.76/14.40 SUBSTF(forall(f), s) -> RON(s, shift) 23.76/14.40 SUBSTF(exists(f), s) -> EXISTS(substf(f, .(1, ron(s, shift)))) 23.76/14.40 SUBSTF(exists(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.40 SUBSTF(exists(f), s) -> .^1(1, ron(s, shift)) 23.76/14.40 SUBSTF(exists(f), s) -> RON(s, shift) 23.76/14.40 SUBSTT(substt(x, s), t) -> SUBSTT(x, ron(s, t)) 23.76/14.40 SUBSTT(substt(x, s), t) -> RON(s, t) 23.76/14.40 SUBSTF(substf(f, s), t) -> SUBSTF(f, ron(s, t)) 23.76/14.40 SUBSTF(substf(f, s), t) -> RON(s, t) 23.76/14.40 RON(ron(s, t), u) -> RON(s, ron(t, u)) 23.76/14.40 RON(ron(s, t), u) -> RON(t, u) 23.76/14.40 RON(.(x, s), t) -> .^1(substt(x, t), ron(s, t)) 23.76/14.40 RON(.(x, s), t) -> SUBSTT(x, t) 23.76/14.40 RON(.(x, s), t) -> RON(s, t) 23.76/14.40 IMP(f, g) -> OR(neg(f), g) 23.76/14.40 IMP(f, g) -> NEG(f) 23.76/14.40 EXISTS(f) -> NEG(forall(neg(f))) 23.76/14.40 EXISTS(f) -> NEG(f) 23.76/14.40 SEQUENT(virg(convf(neg(f)), a), b) -> SEQUENT(a, virg(convf(f), b)) 23.76/14.40 SEQUENT(virg(convf(neg(f)), a), b) -> VIRG(convf(f), b) 23.76/14.40 SEQUENT(convf(neg(f)), b) -> SEQUENT(emptyfset, virg(convf(f), b)) 23.76/14.40 SEQUENT(convf(neg(f)), b) -> VIRG(convf(f), b) 23.76/14.40 SEQUENT(a, virg(convf(neg(f)), b)) -> SEQUENT(virg(convf(f), a), b) 23.76/14.40 SEQUENT(a, virg(convf(neg(f)), b)) -> VIRG(convf(f), a) 23.76/14.40 SEQUENT(a, convf(neg(f))) -> SEQUENT(virg(convf(f), a), emptyfset) 23.76/14.40 SEQUENT(a, convf(neg(f))) -> VIRG(convf(f), a) 23.76/14.40 SEQUENT(virg(convf(and(f, g)), a), b) -> SEQUENT(virg(convf(g), virg(convf(f), a)), b) 23.76/14.40 SEQUENT(virg(convf(and(f, g)), a), b) -> VIRG(convf(g), virg(convf(f), a)) 23.76/14.40 SEQUENT(virg(convf(and(f, g)), a), b) -> VIRG(convf(f), a) 23.76/14.40 SEQUENT(convf(and(f, g)), b) -> SEQUENT(virg(convf(f), convf(g)), b) 23.76/14.40 SEQUENT(convf(and(f, g)), b) -> VIRG(convf(f), convf(g)) 23.76/14.40 SEQUENT(a, virg(convf(or(f, g)), b)) -> SEQUENT(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.40 SEQUENT(a, virg(convf(or(f, g)), b)) -> VIRG(virg(convf(f), convf(g)), b) 23.76/14.40 SEQUENT(a, virg(convf(or(f, g)), b)) -> VIRG(convf(f), convf(g)) 23.76/14.40 SEQUENT(a, convf(or(f, g))) -> SEQUENT(a, virg(convf(f), convf(g))) 23.76/14.40 SEQUENT(a, convf(or(f, g))) -> VIRG(convf(f), convf(g)) 23.76/14.40 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> *^1(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.40 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(f), b))) 23.76/14.40 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> SEQUENT(a, virg(convf(f), b)) 23.76/14.40 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> VIRG(convf(f), b) 23.76/14.40 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(g), b))) 23.76/14.40 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> SEQUENT(a, virg(convf(g), b)) 23.76/14.40 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> VIRG(convf(g), b) 23.76/14.40 CONVS(sequent(a, convf(and(f, g)))) -> *^1(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.40 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(f))) 23.76/14.40 CONVS(sequent(a, convf(and(f, g)))) -> SEQUENT(a, convf(f)) 23.76/14.40 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(g))) 23.76/14.40 CONVS(sequent(a, convf(and(f, g)))) -> SEQUENT(a, convf(g)) 23.76/14.40 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> *^1(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.40 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(f), a), b)) 23.76/14.40 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> SEQUENT(virg(convf(f), a), b) 23.76/14.40 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> VIRG(convf(f), a) 23.76/14.40 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(g), a), b)) 23.76/14.40 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> SEQUENT(virg(convf(g), a), b) 23.76/14.40 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> VIRG(convf(g), a) 23.76/14.40 CONVS(sequent(convf(or(f, g)), b)) -> *^1(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.40 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(f), b)) 23.76/14.40 CONVS(sequent(convf(or(f, g)), b)) -> SEQUENT(convf(f), b) 23.76/14.40 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(g), b)) 23.76/14.40 CONVS(sequent(convf(or(f, g)), b)) -> SEQUENT(convf(g), b) 23.76/14.40 *^1(*(a, a), ext) -> *^1(a, ext) 23.76/14.40 *^1(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.40 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.40 *^1(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.40 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.40 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.40 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.40 *^1(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.40 *^1(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.40 VIRG(virg(a, a), ext) -> VIRG(a, ext) 23.76/14.40 23.76/14.40 The TRS R consists of the following rules: 23.76/14.40 23.76/14.40 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.40 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.40 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.40 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.40 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.40 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.40 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.40 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.40 substt(x, id) -> x 23.76/14.40 substf(f, id) -> f 23.76/14.40 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.40 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.40 substt(1, .(x, s)) -> x 23.76/14.40 ron(id, s) -> s 23.76/14.40 ron(shift, .(x, s)) -> s 23.76/14.40 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.40 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.40 ron(s, id) -> s 23.76/14.40 .(1, shift) -> id 23.76/14.40 .(substt(1, s), ron(shift, s)) -> s 23.76/14.40 virg(emptyfset, a) -> a 23.76/14.40 virg(a, a) -> a 23.76/14.40 *(emptysset, a) -> a 23.76/14.40 *(a, a) -> a 23.76/14.40 neg(neg(f)) -> f 23.76/14.40 and(f, f) -> f 23.76/14.40 or(f, f) -> f 23.76/14.40 imp(f, g) -> or(neg(f), g) 23.76/14.40 exists(f) -> neg(forall(neg(f))) 23.76/14.40 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.40 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.40 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.40 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.40 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.40 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.40 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.40 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.40 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.40 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.40 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.40 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.40 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.40 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.40 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.40 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.40 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.40 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.40 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.40 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.40 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.40 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.40 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.40 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.40 *(*(a, a), ext) -> *(a, ext) 23.76/14.40 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.40 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.40 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.40 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.40 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.40 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.40 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.40 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.40 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.40 23.76/14.40 The set E consists of the following equations: 23.76/14.40 23.76/14.40 *(x, y) == *(y, x) 23.76/14.40 virg(x, y) == virg(y, x) 23.76/14.40 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.40 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.40 23.76/14.40 The set E# consists of the following equations: 23.76/14.40 23.76/14.40 *^1(x, y) == *^1(y, x) 23.76/14.40 VIRG(x, y) == VIRG(y, x) 23.76/14.40 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.40 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.40 23.76/14.40 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.40 23.76/14.40 ---------------------------------------- 23.76/14.40 23.76/14.40 (2) 23.76/14.40 Obligation: 23.76/14.40 The TRS P consists of the following rules: 23.76/14.40 23.76/14.40 SUBSTT(ef(x), y) -> SUBSTT(x, y) 23.76/14.40 SUBSTF(Pe(x), y) -> SUBSTT(x, y) 23.76/14.40 SUBSTF(neg(f), s) -> NEG(substf(f, s)) 23.76/14.40 SUBSTF(neg(f), s) -> SUBSTF(f, s) 23.76/14.40 SUBSTF(and(f, g), s) -> AND(substf(f, s), substf(g, s)) 23.76/14.40 SUBSTF(and(f, g), s) -> SUBSTF(f, s) 23.76/14.40 SUBSTF(and(f, g), s) -> SUBSTF(g, s) 23.76/14.40 SUBSTF(or(f, g), s) -> OR(substf(f, s), substf(g, s)) 23.76/14.40 SUBSTF(or(f, g), s) -> SUBSTF(f, s) 23.76/14.40 SUBSTF(or(f, g), s) -> SUBSTF(g, s) 23.76/14.40 SUBSTF(imp(f, g), s) -> IMP(substf(f, s), substf(g, s)) 23.76/14.40 SUBSTF(imp(f, g), s) -> SUBSTF(f, s) 23.76/14.40 SUBSTF(imp(f, g), s) -> SUBSTF(g, s) 23.76/14.40 SUBSTF(forall(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.40 SUBSTF(forall(f), s) -> .^1(1, ron(s, shift)) 23.76/14.40 SUBSTF(forall(f), s) -> RON(s, shift) 23.76/14.40 SUBSTF(exists(f), s) -> EXISTS(substf(f, .(1, ron(s, shift)))) 23.76/14.40 SUBSTF(exists(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.40 SUBSTF(exists(f), s) -> .^1(1, ron(s, shift)) 23.76/14.41 SUBSTF(exists(f), s) -> RON(s, shift) 23.76/14.41 SUBSTT(substt(x, s), t) -> SUBSTT(x, ron(s, t)) 23.76/14.41 SUBSTT(substt(x, s), t) -> RON(s, t) 23.76/14.41 SUBSTF(substf(f, s), t) -> SUBSTF(f, ron(s, t)) 23.76/14.41 SUBSTF(substf(f, s), t) -> RON(s, t) 23.76/14.41 RON(ron(s, t), u) -> RON(s, ron(t, u)) 23.76/14.41 RON(ron(s, t), u) -> RON(t, u) 23.76/14.41 RON(.(x, s), t) -> .^1(substt(x, t), ron(s, t)) 23.76/14.41 RON(.(x, s), t) -> SUBSTT(x, t) 23.76/14.41 RON(.(x, s), t) -> RON(s, t) 23.76/14.41 IMP(f, g) -> OR(neg(f), g) 23.76/14.41 IMP(f, g) -> NEG(f) 23.76/14.41 EXISTS(f) -> NEG(forall(neg(f))) 23.76/14.41 EXISTS(f) -> NEG(f) 23.76/14.41 SEQUENT(virg(convf(neg(f)), a), b) -> SEQUENT(a, virg(convf(f), b)) 23.76/14.41 SEQUENT(virg(convf(neg(f)), a), b) -> VIRG(convf(f), b) 23.76/14.41 SEQUENT(convf(neg(f)), b) -> SEQUENT(emptyfset, virg(convf(f), b)) 23.76/14.41 SEQUENT(convf(neg(f)), b) -> VIRG(convf(f), b) 23.76/14.41 SEQUENT(a, virg(convf(neg(f)), b)) -> SEQUENT(virg(convf(f), a), b) 23.76/14.41 SEQUENT(a, virg(convf(neg(f)), b)) -> VIRG(convf(f), a) 23.76/14.41 SEQUENT(a, convf(neg(f))) -> SEQUENT(virg(convf(f), a), emptyfset) 23.76/14.41 SEQUENT(a, convf(neg(f))) -> VIRG(convf(f), a) 23.76/14.41 SEQUENT(virg(convf(and(f, g)), a), b) -> SEQUENT(virg(convf(g), virg(convf(f), a)), b) 23.76/14.41 SEQUENT(virg(convf(and(f, g)), a), b) -> VIRG(convf(g), virg(convf(f), a)) 23.76/14.41 SEQUENT(virg(convf(and(f, g)), a), b) -> VIRG(convf(f), a) 23.76/14.41 SEQUENT(convf(and(f, g)), b) -> SEQUENT(virg(convf(f), convf(g)), b) 23.76/14.41 SEQUENT(convf(and(f, g)), b) -> VIRG(convf(f), convf(g)) 23.76/14.41 SEQUENT(a, virg(convf(or(f, g)), b)) -> SEQUENT(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.41 SEQUENT(a, virg(convf(or(f, g)), b)) -> VIRG(virg(convf(f), convf(g)), b) 23.76/14.41 SEQUENT(a, virg(convf(or(f, g)), b)) -> VIRG(convf(f), convf(g)) 23.76/14.41 SEQUENT(a, convf(or(f, g))) -> SEQUENT(a, virg(convf(f), convf(g))) 23.76/14.41 SEQUENT(a, convf(or(f, g))) -> VIRG(convf(f), convf(g)) 23.76/14.41 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> *^1(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.41 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(f), b))) 23.76/14.41 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> SEQUENT(a, virg(convf(f), b)) 23.76/14.41 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> VIRG(convf(f), b) 23.76/14.41 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(g), b))) 23.76/14.41 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> SEQUENT(a, virg(convf(g), b)) 23.76/14.41 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> VIRG(convf(g), b) 23.76/14.41 CONVS(sequent(a, convf(and(f, g)))) -> *^1(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.41 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(f))) 23.76/14.41 CONVS(sequent(a, convf(and(f, g)))) -> SEQUENT(a, convf(f)) 23.76/14.41 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(g))) 23.76/14.41 CONVS(sequent(a, convf(and(f, g)))) -> SEQUENT(a, convf(g)) 23.76/14.41 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> *^1(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.41 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(f), a), b)) 23.76/14.41 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> SEQUENT(virg(convf(f), a), b) 23.76/14.41 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> VIRG(convf(f), a) 23.76/14.41 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(g), a), b)) 23.76/14.41 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> SEQUENT(virg(convf(g), a), b) 23.76/14.41 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> VIRG(convf(g), a) 23.76/14.41 CONVS(sequent(convf(or(f, g)), b)) -> *^1(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.41 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(f), b)) 23.76/14.41 CONVS(sequent(convf(or(f, g)), b)) -> SEQUENT(convf(f), b) 23.76/14.41 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(g), b)) 23.76/14.41 CONVS(sequent(convf(or(f, g)), b)) -> SEQUENT(convf(g), b) 23.76/14.41 *^1(*(a, a), ext) -> *^1(a, ext) 23.76/14.41 *^1(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.41 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.41 *^1(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.41 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.41 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.41 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.41 *^1(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.41 *^1(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.41 VIRG(virg(a, a), ext) -> VIRG(a, ext) 23.76/14.41 23.76/14.41 The TRS R consists of the following rules: 23.76/14.41 23.76/14.41 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.41 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.41 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.41 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.41 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.41 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.41 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.41 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.41 substt(x, id) -> x 23.76/14.41 substf(f, id) -> f 23.76/14.41 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.41 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.41 substt(1, .(x, s)) -> x 23.76/14.41 ron(id, s) -> s 23.76/14.41 ron(shift, .(x, s)) -> s 23.76/14.41 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.41 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.41 ron(s, id) -> s 23.76/14.41 .(1, shift) -> id 23.76/14.41 .(substt(1, s), ron(shift, s)) -> s 23.76/14.41 virg(emptyfset, a) -> a 23.76/14.41 virg(a, a) -> a 23.76/14.41 *(emptysset, a) -> a 23.76/14.41 *(a, a) -> a 23.76/14.41 neg(neg(f)) -> f 23.76/14.41 and(f, f) -> f 23.76/14.41 or(f, f) -> f 23.76/14.41 imp(f, g) -> or(neg(f), g) 23.76/14.41 exists(f) -> neg(forall(neg(f))) 23.76/14.41 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.41 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.41 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.41 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.41 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.41 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.41 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.41 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.41 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.41 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.41 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.41 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.41 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.41 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.41 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.41 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.41 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.41 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.41 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.41 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.41 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.41 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.41 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.41 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.41 *(*(a, a), ext) -> *(a, ext) 23.76/14.41 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.41 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.41 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.41 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.41 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.41 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.41 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.41 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.41 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.41 23.76/14.41 The set E consists of the following equations: 23.76/14.41 23.76/14.41 *(x, y) == *(y, x) 23.76/14.41 virg(x, y) == virg(y, x) 23.76/14.41 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.41 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.41 23.76/14.41 The set E# consists of the following equations: 23.76/14.41 23.76/14.41 *^1(x, y) == *^1(y, x) 23.76/14.41 VIRG(x, y) == VIRG(y, x) 23.76/14.41 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.41 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.41 23.76/14.41 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.41 ---------------------------------------- 23.76/14.41 23.76/14.41 (3) EDependencyGraphProof (EQUIVALENT) 23.76/14.41 The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 42 less nodes. 23.76/14.41 ---------------------------------------- 23.76/14.41 23.76/14.41 (4) 23.76/14.41 Complex Obligation (AND) 23.76/14.41 23.76/14.41 ---------------------------------------- 23.76/14.41 23.76/14.41 (5) 23.76/14.41 Obligation: 23.76/14.41 The TRS P consists of the following rules: 23.76/14.41 23.76/14.41 VIRG(virg(a, a), ext) -> VIRG(a, ext) 23.76/14.41 23.76/14.41 The TRS R consists of the following rules: 23.76/14.41 23.76/14.41 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.41 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.41 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.41 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.41 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.41 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.41 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.41 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.41 substt(x, id) -> x 23.76/14.41 substf(f, id) -> f 23.76/14.41 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.41 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.41 substt(1, .(x, s)) -> x 23.76/14.41 ron(id, s) -> s 23.76/14.41 ron(shift, .(x, s)) -> s 23.76/14.41 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.41 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.41 ron(s, id) -> s 23.76/14.41 .(1, shift) -> id 23.76/14.41 .(substt(1, s), ron(shift, s)) -> s 23.76/14.41 virg(emptyfset, a) -> a 23.76/14.41 virg(a, a) -> a 23.76/14.41 *(emptysset, a) -> a 23.76/14.41 *(a, a) -> a 23.76/14.41 neg(neg(f)) -> f 23.76/14.41 and(f, f) -> f 23.76/14.41 or(f, f) -> f 23.76/14.41 imp(f, g) -> or(neg(f), g) 23.76/14.41 exists(f) -> neg(forall(neg(f))) 23.76/14.41 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.41 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.41 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.41 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.41 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.41 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.41 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.41 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.41 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.41 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.41 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.41 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.41 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.41 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.41 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.41 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.41 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.41 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.41 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.41 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.41 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.41 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.41 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.41 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.41 *(*(a, a), ext) -> *(a, ext) 23.76/14.41 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.41 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.41 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.41 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.41 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.41 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.41 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.41 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.41 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.41 23.76/14.41 The set E consists of the following equations: 23.76/14.41 23.76/14.41 *(x, y) == *(y, x) 23.76/14.41 virg(x, y) == virg(y, x) 23.76/14.41 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.41 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.41 23.76/14.41 The set E# consists of the following equations: 23.76/14.41 23.76/14.41 *^1(x, y) == *^1(y, x) 23.76/14.41 VIRG(x, y) == VIRG(y, x) 23.76/14.41 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.41 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.41 23.76/14.41 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.41 ---------------------------------------- 23.76/14.41 23.76/14.41 (6) ESharpUsableEquationsProof (EQUIVALENT) 23.76/14.41 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 23.76/14.41 *^1(x, y) == *^1(y, x) 23.76/14.41 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.41 23.76/14.41 ---------------------------------------- 23.76/14.41 23.76/14.41 (7) 23.76/14.41 Obligation: 23.76/14.41 The TRS P consists of the following rules: 23.76/14.41 23.76/14.41 VIRG(virg(a, a), ext) -> VIRG(a, ext) 23.76/14.41 23.76/14.41 The TRS R consists of the following rules: 23.76/14.41 23.76/14.41 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.41 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.41 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.41 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.41 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.41 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.41 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.41 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.41 substt(x, id) -> x 23.76/14.41 substf(f, id) -> f 23.76/14.41 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.41 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.41 substt(1, .(x, s)) -> x 23.76/14.41 ron(id, s) -> s 23.76/14.41 ron(shift, .(x, s)) -> s 23.76/14.41 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.41 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.41 ron(s, id) -> s 23.76/14.41 .(1, shift) -> id 23.76/14.41 .(substt(1, s), ron(shift, s)) -> s 23.76/14.41 virg(emptyfset, a) -> a 23.76/14.41 virg(a, a) -> a 23.76/14.41 *(emptysset, a) -> a 23.76/14.41 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (8) EUsableRulesReductionPairsProof (EQUIVALENT) 23.76/14.42 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. 23.76/14.42 23.76/14.42 No dependency pairs are removed. 23.76/14.42 23.76/14.42 The following rules are removed from R: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 The following equations are removed from E: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 Used ordering: POLO with Polynomial interpretation [POLO]: 23.76/14.42 23.76/14.42 POL(VIRG(x_1, x_2)) = 3*x_1 + 3*x_2 23.76/14.42 POL(emptyfset) = 0 23.76/14.42 POL(virg(x_1, x_2)) = x_1 + x_2 23.76/14.42 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (9) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 VIRG(virg(a, a), ext) -> VIRG(a, ext) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 virg(a, a) -> a 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (10) ERuleRemovalProof (EQUIVALENT) 23.76/14.42 By using the rule removal processor [DA_STEIN] with the following polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this EDP problem can be strictly oriented. 23.76/14.42 23.76/14.42 Strictly oriented dependency pairs: 23.76/14.42 23.76/14.42 VIRG(virg(a, a), ext) -> VIRG(a, ext) 23.76/14.42 23.76/14.42 Strictly oriented rules of the TRS R: 23.76/14.42 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 virg(a, a) -> a 23.76/14.42 23.76/14.42 Used ordering: POLO with Polynomial interpretation [POLO]: 23.76/14.42 23.76/14.42 POL(VIRG(x_1, x_2)) = 3*x_1 + 3*x_2 23.76/14.42 POL(virg(x_1, x_2)) = 3 + x_1 + x_2 23.76/14.42 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (11) 23.76/14.42 Obligation: 23.76/14.42 P is empty. 23.76/14.42 R is empty. 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (12) PisEmptyProof (EQUIVALENT) 23.76/14.42 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (13) 23.76/14.42 YES 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (14) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 *^1(*(a, a), ext) -> *^1(a, ext) 23.76/14.42 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.42 *^1(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.42 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *^1(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 *^1(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.42 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *^1(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (15) ESharpUsableEquationsProof (EQUIVALENT) 23.76/14.42 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (16) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 *^1(*(a, a), ext) -> *^1(a, ext) 23.76/14.42 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.42 *^1(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.42 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *^1(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 *^1(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.42 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *^1(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (17) EDPPoloProof (EQUIVALENT) 23.76/14.42 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 23.76/14.42 23.76/14.42 23.76/14.42 *^1(*(a, a), ext) -> *^1(a, ext) 23.76/14.42 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.42 *^1(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.42 *^1(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *^1(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 *^1(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, b)), ext) 23.76/14.42 *^1(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *^1(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *^1(convs(sequent(a, emptyfset)), ext) 23.76/14.42 With the implicit AFS we had to orient the following set of usable rules of R non-strictly. 23.76/14.42 23.76/14.42 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(a, a) -> a 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 We had to orient the following equations of E# equivalently. 23.76/14.42 23.76/14.42 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 With the implicit AFS we had to orient the following usable equations of E equivalently. 23.76/14.42 23.76/14.42 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 Used ordering: POLO with Polynomial interpretation [POLO]: 23.76/14.42 23.76/14.42 POL(*(x_1, x_2)) = 1 + x_1 + x_2 23.76/14.42 POL(*^1(x_1, x_2)) = x_1 + x_2 23.76/14.42 POL(and(x_1, x_2)) = 1 + x_1 + x_1*x_2 + x_2 23.76/14.42 POL(convf(x_1)) = x_1^2 23.76/14.42 POL(convs(x_1)) = x_1 23.76/14.42 POL(emptyfset) = 0 23.76/14.42 POL(emptysset) = 0 23.76/14.42 POL(neg(x_1)) = x_1 23.76/14.42 POL(or(x_1, x_2)) = 1 + x_1 + x_1*x_2 + x_2 23.76/14.42 POL(sequent(x_1, x_2)) = x_1 + x_1*x_2 + x_2 23.76/14.42 POL(virg(x_1, x_2)) = x_1 + x_1*x_2 + x_2 23.76/14.42 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (18) 23.76/14.42 Obligation: 23.76/14.42 P is empty. 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (19) PisEmptyProof (EQUIVALENT) 23.76/14.42 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (20) 23.76/14.42 YES 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (21) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 SEQUENT(convf(neg(f)), b) -> SEQUENT(emptyfset, virg(convf(f), b)) 23.76/14.42 SEQUENT(a, virg(convf(neg(f)), b)) -> SEQUENT(virg(convf(f), a), b) 23.76/14.42 SEQUENT(a, convf(neg(f))) -> SEQUENT(virg(convf(f), a), emptyfset) 23.76/14.42 SEQUENT(virg(convf(neg(f)), a), b) -> SEQUENT(a, virg(convf(f), b)) 23.76/14.42 SEQUENT(virg(convf(and(f, g)), a), b) -> SEQUENT(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 SEQUENT(convf(and(f, g)), b) -> SEQUENT(virg(convf(f), convf(g)), b) 23.76/14.42 SEQUENT(a, virg(convf(or(f, g)), b)) -> SEQUENT(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 SEQUENT(a, convf(or(f, g))) -> SEQUENT(a, virg(convf(f), convf(g))) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (22) ESharpUsableEquationsProof (EQUIVALENT) 23.76/14.42 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (23) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 SEQUENT(convf(neg(f)), b) -> SEQUENT(emptyfset, virg(convf(f), b)) 23.76/14.42 SEQUENT(a, virg(convf(neg(f)), b)) -> SEQUENT(virg(convf(f), a), b) 23.76/14.42 SEQUENT(a, convf(neg(f))) -> SEQUENT(virg(convf(f), a), emptyfset) 23.76/14.42 SEQUENT(virg(convf(neg(f)), a), b) -> SEQUENT(a, virg(convf(f), b)) 23.76/14.42 SEQUENT(virg(convf(and(f, g)), a), b) -> SEQUENT(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 SEQUENT(convf(and(f, g)), b) -> SEQUENT(virg(convf(f), convf(g)), b) 23.76/14.42 SEQUENT(a, virg(convf(or(f, g)), b)) -> SEQUENT(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 SEQUENT(a, convf(or(f, g))) -> SEQUENT(a, virg(convf(f), convf(g))) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 E# is empty. 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (24) EUsableRulesReductionPairsProof (EQUIVALENT) 23.76/14.42 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. 23.76/14.42 23.76/14.42 The following dependency pairs can be deleted: 23.76/14.42 23.76/14.42 SEQUENT(convf(neg(f)), b) -> SEQUENT(emptyfset, virg(convf(f), b)) 23.76/14.42 SEQUENT(a, virg(convf(neg(f)), b)) -> SEQUENT(virg(convf(f), a), b) 23.76/14.42 SEQUENT(a, convf(neg(f))) -> SEQUENT(virg(convf(f), a), emptyfset) 23.76/14.42 SEQUENT(virg(convf(neg(f)), a), b) -> SEQUENT(a, virg(convf(f), b)) 23.76/14.42 SEQUENT(virg(convf(and(f, g)), a), b) -> SEQUENT(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 SEQUENT(convf(and(f, g)), b) -> SEQUENT(virg(convf(f), convf(g)), b) 23.76/14.42 SEQUENT(a, virg(convf(or(f, g)), b)) -> SEQUENT(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 SEQUENT(a, convf(or(f, g))) -> SEQUENT(a, virg(convf(f), convf(g))) 23.76/14.42 The following rules are removed from R: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 The following equations are removed from E: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 Used ordering: POLO with Polynomial interpretation [POLO]: 23.76/14.42 23.76/14.42 POL(SEQUENT(x_1, x_2)) = 2*x_1 + x_2 23.76/14.42 POL(and(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 23.76/14.42 POL(convf(x_1)) = x_1 23.76/14.42 POL(emptyfset) = 0 23.76/14.42 POL(neg(x_1)) = 1 + 3*x_1 23.76/14.42 POL(or(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 23.76/14.42 POL(virg(x_1, x_2)) = x_1 + x_2 23.76/14.42 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (25) 23.76/14.42 Obligation: 23.76/14.42 P is empty. 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 virg(a, a) -> a 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 E# is empty. 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (26) PisEmptyProof (EQUIVALENT) 23.76/14.42 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (27) 23.76/14.42 YES 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (28) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(g))) 23.76/14.42 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(g), b))) 23.76/14.42 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(f), b)) 23.76/14.42 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(f), b))) 23.76/14.42 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(g), a), b)) 23.76/14.42 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(f), a), b)) 23.76/14.42 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(g), b)) 23.76/14.42 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(f))) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (29) ESharpUsableEquationsProof (EQUIVALENT) 23.76/14.42 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (30) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(g))) 23.76/14.42 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(g), b))) 23.76/14.42 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(f), b)) 23.76/14.42 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(f), b))) 23.76/14.42 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(g), a), b)) 23.76/14.42 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(f), a), b)) 23.76/14.42 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(g), b)) 23.76/14.42 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(f))) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 E# is empty. 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (31) EUsableRulesReductionPairsProof (EQUIVALENT) 23.76/14.42 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. 23.76/14.42 23.76/14.42 The following dependency pairs can be deleted: 23.76/14.42 23.76/14.42 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(g))) 23.76/14.42 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(g), b))) 23.76/14.42 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(f), b)) 23.76/14.42 CONVS(sequent(a, virg(convf(and(f, g)), b))) -> CONVS(sequent(a, virg(convf(f), b))) 23.76/14.42 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(g), a), b)) 23.76/14.42 CONVS(sequent(virg(convf(or(f, g)), a), b)) -> CONVS(sequent(virg(convf(f), a), b)) 23.76/14.42 CONVS(sequent(convf(or(f, g)), b)) -> CONVS(sequent(convf(g), b)) 23.76/14.42 CONVS(sequent(a, convf(and(f, g)))) -> CONVS(sequent(a, convf(f))) 23.76/14.42 The following rules are removed from R: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 The following equations are removed from E: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 Used ordering: POLO with Polynomial interpretation [POLO]: 23.76/14.42 23.76/14.42 POL(CONVS(x_1)) = x_1 23.76/14.42 POL(and(x_1, x_2)) = 3 + 2*x_1 + x_2 23.76/14.42 POL(convf(x_1)) = 2 + 3*x_1 23.76/14.42 POL(emptyfset) = 0 23.76/14.42 POL(neg(x_1)) = 2*x_1 23.76/14.42 POL(or(x_1, x_2)) = 3 + 2*x_1 + 2*x_2 23.76/14.42 POL(sequent(x_1, x_2)) = 2*x_1 + 2*x_2 23.76/14.42 POL(virg(x_1, x_2)) = x_1 + x_2 23.76/14.42 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (32) 23.76/14.42 Obligation: 23.76/14.42 P is empty. 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 virg(a, a) -> a 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 E# is empty. 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (33) PisEmptyProof (EQUIVALENT) 23.76/14.42 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (34) 23.76/14.42 YES 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (35) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 RON(.(x, s), t) -> SUBSTT(x, t) 23.76/14.42 RON(ron(s, t), u) -> RON(t, u) 23.76/14.42 RON(ron(s, t), u) -> RON(s, ron(t, u)) 23.76/14.42 SUBSTT(ef(x), y) -> SUBSTT(x, y) 23.76/14.42 SUBSTT(substt(x, s), t) -> RON(s, t) 23.76/14.42 RON(.(x, s), t) -> RON(s, t) 23.76/14.42 SUBSTT(substt(x, s), t) -> SUBSTT(x, ron(s, t)) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (36) ESharpUsableEquationsProof (EQUIVALENT) 23.76/14.42 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (37) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 RON(.(x, s), t) -> SUBSTT(x, t) 23.76/14.42 RON(ron(s, t), u) -> RON(t, u) 23.76/14.42 RON(ron(s, t), u) -> RON(s, ron(t, u)) 23.76/14.42 SUBSTT(ef(x), y) -> SUBSTT(x, y) 23.76/14.42 SUBSTT(substt(x, s), t) -> RON(s, t) 23.76/14.42 RON(.(x, s), t) -> RON(s, t) 23.76/14.42 SUBSTT(substt(x, s), t) -> SUBSTT(x, ron(s, t)) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 E# is empty. 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (38) EDPPoloProof (EQUIVALENT) 23.76/14.42 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. The following set of Dependency Pairs of this DP problem can be strictly oriented. 23.76/14.42 23.76/14.42 23.76/14.42 RON(.(x, s), t) -> SUBSTT(x, t) 23.76/14.42 RON(ron(s, t), u) -> RON(t, u) 23.76/14.42 RON(ron(s, t), u) -> RON(s, ron(t, u)) 23.76/14.42 SUBSTT(substt(x, s), t) -> RON(s, t) 23.76/14.42 RON(.(x, s), t) -> RON(s, t) 23.76/14.42 SUBSTT(substt(x, s), t) -> SUBSTT(x, ron(s, t)) 23.76/14.42 The remaining Dependency Pairs were at least non-strictly oriented. 23.76/14.42 23.76/14.42 23.76/14.42 SUBSTT(ef(x), y) -> SUBSTT(x, y) 23.76/14.42 With the implicit AFS there is no usable rule of R. 23.76/14.42 23.76/14.42 23.76/14.42 There is no equation of E#. 23.76/14.42 23.76/14.42 23.76/14.42 With the implicit AFS there is no usable equation of E. 23.76/14.42 23.76/14.42 23.76/14.42 Used ordering: POLO with Polynomial interpretation [POLO]: 23.76/14.42 23.76/14.42 POL(.(x_1, x_2)) = 1 + x_1 + x_2 23.76/14.42 POL(1) = 3 23.76/14.42 POL(RON(x_1, x_2)) = 3 + x_1 23.76/14.42 POL(SUBSTT(x_1, x_2)) = 3 + x_1 23.76/14.42 POL(ef(x_1)) = 2*x_1 23.76/14.42 POL(id) = 3 23.76/14.42 POL(ron(x_1, x_2)) = 1 + x_1 + 2*x_2 23.76/14.42 POL(shift) = 3 23.76/14.42 POL(substt(x_1, x_2)) = 1 + x_1 + x_2 23.76/14.42 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (39) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 SUBSTT(ef(x), y) -> SUBSTT(x, y) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 E# is empty. 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (40) EUsableRulesReductionPairsProof (EQUIVALENT) 23.76/14.42 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. 23.76/14.42 23.76/14.42 The following dependency pairs can be deleted: 23.76/14.42 23.76/14.42 SUBSTT(ef(x), y) -> SUBSTT(x, y) 23.76/14.42 The following rules are removed from R: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 The following equations are removed from E: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 Used ordering: POLO with Polynomial interpretation [POLO]: 23.76/14.42 23.76/14.42 POL(SUBSTT(x_1, x_2)) = 3*x_1 + x_2 23.76/14.42 POL(ef(x_1)) = 3*x_1 23.76/14.42 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (41) 23.76/14.42 Obligation: 23.76/14.42 P is empty. 23.76/14.42 R is empty. 23.76/14.42 E is empty. 23.76/14.42 E# is empty. 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (42) PisEmptyProof (EQUIVALENT) 23.76/14.42 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (43) 23.76/14.42 YES 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (44) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 SUBSTF(neg(f), s) -> SUBSTF(f, s) 23.76/14.42 SUBSTF(or(f, g), s) -> SUBSTF(g, s) 23.76/14.42 SUBSTF(and(f, g), s) -> SUBSTF(f, s) 23.76/14.42 SUBSTF(imp(f, g), s) -> SUBSTF(g, s) 23.76/14.42 SUBSTF(or(f, g), s) -> SUBSTF(f, s) 23.76/14.42 SUBSTF(and(f, g), s) -> SUBSTF(g, s) 23.76/14.42 SUBSTF(imp(f, g), s) -> SUBSTF(f, s) 23.76/14.42 SUBSTF(forall(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.42 SUBSTF(exists(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.42 SUBSTF(substf(f, s), t) -> SUBSTF(f, ron(s, t)) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.42 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.42 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.42 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.42 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.42 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.42 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.42 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.42 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.42 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.42 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.42 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.42 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.42 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.42 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.42 *(*(a, a), ext) -> *(a, ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.42 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.42 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.42 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.42 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.42 23.76/14.42 The set E consists of the following equations: 23.76/14.42 23.76/14.42 *(x, y) == *(y, x) 23.76/14.42 virg(x, y) == virg(y, x) 23.76/14.42 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.42 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.42 23.76/14.42 The set E# consists of the following equations: 23.76/14.42 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (45) ESharpUsableEquationsProof (EQUIVALENT) 23.76/14.42 We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: 23.76/14.42 *^1(x, y) == *^1(y, x) 23.76/14.42 VIRG(x, y) == VIRG(y, x) 23.76/14.42 *^1(*(x, y), z) == *^1(x, *(y, z)) 23.76/14.42 VIRG(virg(x, y), z) == VIRG(x, virg(y, z)) 23.76/14.42 23.76/14.42 ---------------------------------------- 23.76/14.42 23.76/14.42 (46) 23.76/14.42 Obligation: 23.76/14.42 The TRS P consists of the following rules: 23.76/14.42 23.76/14.42 SUBSTF(neg(f), s) -> SUBSTF(f, s) 23.76/14.42 SUBSTF(or(f, g), s) -> SUBSTF(g, s) 23.76/14.42 SUBSTF(and(f, g), s) -> SUBSTF(f, s) 23.76/14.42 SUBSTF(imp(f, g), s) -> SUBSTF(g, s) 23.76/14.42 SUBSTF(or(f, g), s) -> SUBSTF(f, s) 23.76/14.42 SUBSTF(and(f, g), s) -> SUBSTF(g, s) 23.76/14.42 SUBSTF(imp(f, g), s) -> SUBSTF(f, s) 23.76/14.42 SUBSTF(forall(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.42 SUBSTF(exists(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.42 SUBSTF(substf(f, s), t) -> SUBSTF(f, ron(s, t)) 23.76/14.42 23.76/14.42 The TRS R consists of the following rules: 23.76/14.42 23.76/14.42 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.42 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.42 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.42 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.42 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.42 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.42 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.42 substt(x, id) -> x 23.76/14.42 substf(f, id) -> f 23.76/14.42 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.42 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.42 substt(1, .(x, s)) -> x 23.76/14.42 ron(id, s) -> s 23.76/14.42 ron(shift, .(x, s)) -> s 23.76/14.42 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.42 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.42 ron(s, id) -> s 23.76/14.42 .(1, shift) -> id 23.76/14.42 .(substt(1, s), ron(shift, s)) -> s 23.76/14.42 virg(emptyfset, a) -> a 23.76/14.42 virg(a, a) -> a 23.76/14.42 *(emptysset, a) -> a 23.76/14.42 *(a, a) -> a 23.76/14.42 neg(neg(f)) -> f 23.76/14.42 and(f, f) -> f 23.76/14.42 or(f, f) -> f 23.76/14.42 imp(f, g) -> or(neg(f), g) 23.76/14.42 exists(f) -> neg(forall(neg(f))) 23.76/14.42 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.42 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.42 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.42 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.42 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.43 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.43 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.43 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.43 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.43 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.43 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.43 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.43 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.43 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.43 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.43 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.43 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.43 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.43 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.43 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.43 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.43 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.43 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.43 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.43 *(*(a, a), ext) -> *(a, ext) 23.76/14.43 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.43 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.43 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.43 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.43 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.43 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.43 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.43 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.43 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.43 23.76/14.43 The set E consists of the following equations: 23.76/14.43 23.76/14.43 *(x, y) == *(y, x) 23.76/14.43 virg(x, y) == virg(y, x) 23.76/14.43 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.43 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.43 23.76/14.43 E# is empty. 23.76/14.43 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.43 ---------------------------------------- 23.76/14.43 23.76/14.43 (47) EDPPoloProof (EQUIVALENT) 23.76/14.43 We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. 23.76/14.43 23.76/14.43 23.76/14.43 SUBSTF(neg(f), s) -> SUBSTF(f, s) 23.76/14.43 SUBSTF(or(f, g), s) -> SUBSTF(g, s) 23.76/14.43 SUBSTF(and(f, g), s) -> SUBSTF(f, s) 23.76/14.43 SUBSTF(imp(f, g), s) -> SUBSTF(g, s) 23.76/14.43 SUBSTF(or(f, g), s) -> SUBSTF(f, s) 23.76/14.43 SUBSTF(and(f, g), s) -> SUBSTF(g, s) 23.76/14.43 SUBSTF(imp(f, g), s) -> SUBSTF(f, s) 23.76/14.43 SUBSTF(forall(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.43 SUBSTF(exists(f), s) -> SUBSTF(f, .(1, ron(s, shift))) 23.76/14.43 SUBSTF(substf(f, s), t) -> SUBSTF(f, ron(s, t)) 23.76/14.43 With the implicit AFS there is no usable rule of R. 23.76/14.43 23.76/14.43 23.76/14.43 There is no equation of E#. 23.76/14.43 23.76/14.43 23.76/14.43 With the implicit AFS there is no usable equation of E. 23.76/14.43 23.76/14.43 23.76/14.43 Used ordering: POLO with Polynomial interpretation [POLO]: 23.76/14.43 23.76/14.43 POL(.(x_1, x_2)) = 0 23.76/14.43 POL(1) = 0 23.76/14.43 POL(SUBSTF(x_1, x_2)) = 3*x_1 23.76/14.43 POL(and(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 23.76/14.43 POL(ef(x_1)) = 0 23.76/14.43 POL(exists(x_1)) = 1 + 3*x_1 23.76/14.43 POL(forall(x_1)) = 1 + 3*x_1 23.76/14.43 POL(id) = 3 23.76/14.43 POL(imp(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 23.76/14.43 POL(neg(x_1)) = 2 + 2*x_1 23.76/14.43 POL(or(x_1, x_2)) = 2 + 2*x_1 + 3*x_2 23.76/14.43 POL(ron(x_1, x_2)) = 0 23.76/14.43 POL(shift) = 0 23.76/14.43 POL(substf(x_1, x_2)) = 2 + 2*x_1 + x_2 23.76/14.43 POL(substt(x_1, x_2)) = 0 23.76/14.43 23.76/14.43 23.76/14.43 ---------------------------------------- 23.76/14.43 23.76/14.43 (48) 23.76/14.43 Obligation: 23.76/14.43 P is empty. 23.76/14.43 The TRS R consists of the following rules: 23.76/14.43 23.76/14.43 substt(ef(x), y) -> ef(substt(x, y)) 23.76/14.43 substf(Pe(x), y) -> Pe(substt(x, y)) 23.76/14.43 substf(neg(f), s) -> neg(substf(f, s)) 23.76/14.43 substf(and(f, g), s) -> and(substf(f, s), substf(g, s)) 23.76/14.43 substf(or(f, g), s) -> or(substf(f, s), substf(g, s)) 23.76/14.43 substf(imp(f, g), s) -> imp(substf(f, s), substf(g, s)) 23.76/14.43 substf(forall(f), s) -> forall(substf(f, .(1, ron(s, shift)))) 23.76/14.43 substf(exists(f), s) -> exists(substf(f, .(1, ron(s, shift)))) 23.76/14.43 substt(x, id) -> x 23.76/14.43 substf(f, id) -> f 23.76/14.43 substt(substt(x, s), t) -> substt(x, ron(s, t)) 23.76/14.43 substf(substf(f, s), t) -> substf(f, ron(s, t)) 23.76/14.43 substt(1, .(x, s)) -> x 23.76/14.43 ron(id, s) -> s 23.76/14.43 ron(shift, .(x, s)) -> s 23.76/14.43 ron(ron(s, t), u) -> ron(s, ron(t, u)) 23.76/14.43 ron(.(x, s), t) -> .(substt(x, t), ron(s, t)) 23.76/14.43 ron(s, id) -> s 23.76/14.43 .(1, shift) -> id 23.76/14.43 .(substt(1, s), ron(shift, s)) -> s 23.76/14.43 virg(emptyfset, a) -> a 23.76/14.43 virg(a, a) -> a 23.76/14.43 *(emptysset, a) -> a 23.76/14.43 *(a, a) -> a 23.76/14.43 neg(neg(f)) -> f 23.76/14.43 and(f, f) -> f 23.76/14.43 or(f, f) -> f 23.76/14.43 imp(f, g) -> or(neg(f), g) 23.76/14.43 exists(f) -> neg(forall(neg(f))) 23.76/14.43 sequent(virg(convf(neg(f)), a), b) -> sequent(a, virg(convf(f), b)) 23.76/14.43 sequent(convf(neg(f)), b) -> sequent(emptyfset, virg(convf(f), b)) 23.76/14.43 sequent(a, virg(convf(neg(f)), b)) -> sequent(virg(convf(f), a), b) 23.76/14.43 sequent(a, convf(neg(f))) -> sequent(virg(convf(f), a), emptyfset) 23.76/14.43 sequent(virg(convf(and(f, g)), a), b) -> sequent(virg(convf(g), virg(convf(f), a)), b) 23.76/14.43 sequent(convf(and(f, g)), b) -> sequent(virg(convf(f), convf(g)), b) 23.76/14.43 sequent(a, virg(convf(or(f, g)), b)) -> sequent(a, virg(virg(convf(f), convf(g)), b)) 23.76/14.43 sequent(a, convf(or(f, g))) -> sequent(a, virg(convf(f), convf(g))) 23.76/14.43 convs(sequent(a, virg(convf(and(f, g)), b))) -> *(convs(sequent(a, virg(convf(f), b))), convs(sequent(a, virg(convf(g), b)))) 23.76/14.43 convs(sequent(a, convf(and(f, g)))) -> *(convs(sequent(a, convf(f))), convs(sequent(a, convf(g)))) 23.76/14.43 convs(sequent(virg(convf(or(f, g)), a), b)) -> *(convs(sequent(virg(convf(f), a), b)), convs(sequent(virg(convf(g), a), b))) 23.76/14.43 convs(sequent(convf(or(f, g)), b)) -> *(convs(sequent(convf(f), b)), convs(sequent(convf(g), b))) 23.76/14.43 convs(sequent(virg(convf(f), a), virg(convf(f), b))) -> emptysset 23.76/14.43 convs(sequent(virg(convf(f), a), convf(f))) -> emptysset 23.76/14.43 convs(sequent(convf(f), virg(convf(f), b))) -> emptysset 23.76/14.43 convs(sequent(convf(f), convf(f))) -> emptysset 23.76/14.43 *(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.43 *(convs(sequent(virg(f, a), b)), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.43 *(convs(sequent(a, virg(f, b))), convs(sequent(a, b))) -> convs(sequent(a, b)) 23.76/14.43 *(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))) -> convs(sequent(a, emptyfset)) 23.76/14.43 *(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))) -> convs(sequent(emptyfset, b)) 23.76/14.43 *(convs(sequent(emptyfset, b)), convs(sequent(a, b))) -> convs(sequent(emptyfset, b)) 23.76/14.43 *(convs(sequent(a, emptyfset)), convs(sequent(a, b))) -> convs(sequent(a, emptyfset)) 23.76/14.43 *(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))) -> convs(sequent(emptyfset, emptyfset)) 23.76/14.43 *(*(a, a), ext) -> *(a, ext) 23.76/14.43 *(*(convs(sequent(virg(f, a), virg(g, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.43 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.43 *(*(convs(sequent(a, virg(f, b))), convs(sequent(a, b))), ext) -> *(convs(sequent(a, b)), ext) 23.76/14.43 *(*(convs(sequent(virg(f, a), b)), convs(sequent(a, emptyfset))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.43 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, virg(f, b)))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.43 *(*(convs(sequent(emptyfset, b)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, b)), ext) 23.76/14.43 *(*(convs(sequent(a, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(a, emptyfset)), ext) 23.76/14.43 *(*(convs(sequent(emptyfset, emptyfset)), convs(sequent(a, b))), ext) -> *(convs(sequent(emptyfset, emptyfset)), ext) 23.76/14.43 virg(virg(a, a), ext) -> virg(a, ext) 23.76/14.43 23.76/14.43 The set E consists of the following equations: 23.76/14.43 23.76/14.43 *(x, y) == *(y, x) 23.76/14.43 virg(x, y) == virg(y, x) 23.76/14.43 *(*(x, y), z) == *(x, *(y, z)) 23.76/14.43 virg(virg(x, y), z) == virg(x, virg(y, z)) 23.76/14.43 23.76/14.43 E# is empty. 23.76/14.43 We have to consider all minimal (P,E#,R,E)-chains 23.76/14.43 ---------------------------------------- 23.76/14.43 23.76/14.43 (49) PisEmptyProof (EQUIVALENT) 23.76/14.43 The TRS P is empty. Hence, there is no (P,E#,R,E) chain. 23.76/14.43 ---------------------------------------- 23.76/14.43 23.76/14.43 (50) 23.76/14.43 YES 24.01/14.48 EOF