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