YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination of the given ETRS could be proven:

(0) ETRS
(1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms]
(2) EDP
(3) EDependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) EDP
        (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (7) EDP
        (8) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (9) EDP
        (10) PisEmptyProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) EDP
        (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (14) EDP
        (15) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (16) EDP
        (17) PisEmptyProof [EQUIVALENT, 0 ms]
        (18) YES
    (19) EDP
        (20) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (21) EDP
        (22) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
        (23) EDP
        (24) PisEmptyProof [EQUIVALENT, 0 ms]
        (25) YES
    (26) EDP
        (27) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
        (28) EDP
        (29) EDPPoloProof [EQUIVALENT, 0 ms]
        (30) EDP
        (31) EDependencyGraphProof [EQUIVALENT, 0 ms]
        (32) EDP
        (33) EDPPoloProof [EQUIVALENT, 0 ms]
        (34) EDP
        (35) EDependencyGraphProof [EQUIVALENT, 0 ms]
        (36) TRUE


----------------------------------------

(0)
Obligation:
Equational rewrite system:
The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(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:

   EQ(s(x), s(y)) -> EQ(x, y)
   UNION(edge(x, y, i), h) -> UNION(i, h)
   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
   REACH(x, y, edge(u, v, i), h) -> EQ(x, u)
   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
   IF_REACH_1(true, x, y, edge(u, v, i), h) -> EQ(y, v)
   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> OR(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> UNION(i, h)
   OR(or(true, y), ext) -> OR(true, ext)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)
   OR(x, y) == OR(y, x)
   OR(or(x, y), z) == OR(x, or(y, z))

We have to consider all minimal (P,E#,R,E)-chains

----------------------------------------

(2)
Obligation:
The TRS P consists of the following rules:

   EQ(s(x), s(y)) -> EQ(x, y)
   UNION(edge(x, y, i), h) -> UNION(i, h)
   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
   REACH(x, y, edge(u, v, i), h) -> EQ(x, u)
   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
   IF_REACH_1(true, x, y, edge(u, v, i), h) -> EQ(y, v)
   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> OR(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> UNION(i, h)
   OR(or(true, y), ext) -> OR(true, ext)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)
   OR(x, y) == OR(y, x)
   OR(or(x, y), z) == OR(x, or(y, z))

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(3) EDependencyGraphProof (EQUIVALENT)
The approximation of the Equational Dependency Graph [DA_STEIN] contains 4 SCCs with 4 less nodes.
----------------------------------------

(4)
Complex Obligation (AND)

----------------------------------------

(5)
Obligation:
The TRS P consists of the following rules:

   OR(or(true, y), ext) -> OR(true, ext)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)
   OR(x, y) == OR(y, x)
   OR(or(x, y), z) == OR(x, or(y, z))

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(6) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   EQ(x, y) == EQ(y, x)

----------------------------------------

(7)
Obligation:
The TRS P consists of the following rules:

   OR(or(true, y), ext) -> OR(true, ext)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

The set E# consists of the following equations:

   OR(or(x, y), z) == OR(x, or(y, z))
   OR(x, y) == OR(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(8) EUsableRulesReductionPairsProof (EQUIVALENT)
By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the  usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.

The following dependency pairs can be deleted:

   OR(or(true, y), ext) -> OR(true, ext)
The following rules are removed from R:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)
The following equations are removed from E:

   eq(x, y) == eq(y, x)
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(OR(x_1, x_2)) = 2*x_1 + 2*x_2
   POL(false) = 0
   POL(or(x_1, x_2)) = 2 + x_1 + x_2
   POL(true) = 0


----------------------------------------

(9)
Obligation:
P is empty.
R is empty.
The set E consists of the following equations:

   or(or(x, y), z) == or(x, or(y, z))
   or(x, y) == or(y, x)

The set E# consists of the following equations:

   OR(or(x, y), z) == OR(x, or(y, z))
   OR(x, y) == OR(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(10) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(11)
YES

----------------------------------------

(12)
Obligation:
The TRS P consists of the following rules:

   UNION(edge(x, y, i), h) -> UNION(i, h)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)
   OR(x, y) == OR(y, x)
   OR(or(x, y), z) == OR(x, or(y, z))

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(13) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   EQ(x, y) == EQ(y, x)
   OR(x, y) == OR(y, x)
   OR(or(x, y), z) == OR(x, or(y, z))

----------------------------------------

(14)
Obligation:
The TRS P consists of the following rules:

   UNION(edge(x, y, i), h) -> UNION(i, h)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

E# is empty.
We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(15) 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:

   UNION(edge(x, y, i), h) -> UNION(i, h)
The following rules are removed from R:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)
The following equations are removed from E:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(UNION(x_1, x_2)) = 3*x_1 + x_2
   POL(edge(x_1, x_2, x_3)) = x_1 + x_2 + 3*x_3


----------------------------------------

(16)
Obligation:
P is empty.
R is empty.
E is empty.
E# is empty.
We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(17) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(18)
YES

----------------------------------------

(19)
Obligation:
The TRS P consists of the following rules:

   EQ(s(x), s(y)) -> EQ(x, y)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)
   OR(x, y) == OR(y, x)
   OR(or(x, y), z) == OR(x, or(y, z))

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(20) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   OR(x, y) == OR(y, x)
   OR(or(x, y), z) == OR(x, or(y, z))

----------------------------------------

(21)
Obligation:
The TRS P consists of the following rules:

   EQ(s(x), s(y)) -> EQ(x, y)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(22) 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:

   EQ(s(x), s(y)) -> EQ(x, y)
The following rules are removed from R:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)
The following equations are removed from E:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))
Used ordering: POLO with Polynomial interpretation [POLO]:

   POL(EQ(x_1, x_2)) = 3*x_1 + 3*x_2
   POL(s(x_1)) = 3*x_1


----------------------------------------

(23)
Obligation:
P is empty.
R is empty.
E is empty.
The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(24) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
----------------------------------------

(25)
YES

----------------------------------------

(26)
Obligation:
The TRS P consists of the following rules:

   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

The set E# consists of the following equations:

   EQ(x, y) == EQ(y, x)
   OR(x, y) == OR(y, x)
   OR(or(x, y), z) == OR(x, or(y, z))

We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(27) ESharpUsableEquationsProof (EQUIVALENT)
We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
   EQ(x, y) == EQ(y, x)
   OR(x, y) == OR(y, x)
   OR(or(x, y), z) == OR(x, or(y, z))

----------------------------------------

(28)
Obligation:
The TRS P consists of the following rules:

   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

E# is empty.
We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(29) 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.


   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)
The remaining Dependency Pairs were at least non-strictly oriented.


   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
With the implicit AFS we had to orient the following set of usable rules of R non-strictly.


   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
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(0) = 0
   POL(IF_REACH_1(x_1, x_2, x_3, x_4, x_5)) = 3*x_3 + 2*x_4 + 2*x_5
   POL(IF_REACH_2(x_1, x_2, x_3, x_4, x_5)) = 3*x_3 + 2*x_4 + 2*x_5
   POL(REACH(x_1, x_2, x_3, x_4)) = 3*x_2 + 2*x_3 + 2*x_4
   POL(edge(x_1, x_2, x_3)) = 1 + x_3
   POL(empty) = 0
   POL(eq(x_1, x_2)) = 0
   POL(false) = 0
   POL(s(x_1)) = 0
   POL(true) = 0
   POL(union(x_1, x_2)) = x_1 + x_2


----------------------------------------

(30)
Obligation:
The TRS P consists of the following rules:

   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

E# is empty.
We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(31) EDependencyGraphProof (EQUIVALENT)
The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 1 less node.
----------------------------------------

(32)
Obligation:
The TRS P consists of the following rules:

   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

E# is empty.
We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(33) 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.


   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
The remaining Dependency Pairs were at least non-strictly oriented.


   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
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(0) = 0
   POL(IF_REACH_1(x_1, x_2, x_3, x_4, x_5)) = 1 + 3*x_2 + x_4
   POL(REACH(x_1, x_2, x_3, x_4)) = 2 + 3*x_1 + 3*x_3
   POL(edge(x_1, x_2, x_3)) = 1 + 2*x_2 + 3*x_3
   POL(eq(x_1, x_2)) = 0
   POL(false) = 0
   POL(s(x_1)) = 0
   POL(true) = 3


----------------------------------------

(34)
Obligation:
The TRS P consists of the following rules:

   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))

The TRS R consists of the following rules:

   eq(0, 0) -> true
   eq(0, s(x)) -> false
   eq(s(x), 0) -> false
   eq(s(x), s(y)) -> eq(x, y)
   or(true, y) -> true
   or(false, y) -> y
   union(empty, h) -> h
   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
   reach(x, y, empty, h) -> false
   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
   if_reach_2(true, x, y, edge(u, v, i), h) -> true
   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
   or(or(true, y), ext) -> or(true, ext)

The set E consists of the following equations:

   eq(x, y) == eq(y, x)
   or(x, y) == or(y, x)
   or(or(x, y), z) == or(x, or(y, z))

E# is empty.
We have to consider all minimal (P,E#,R,E)-chains
----------------------------------------

(35) EDependencyGraphProof (EQUIVALENT)
The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 1 less node.
----------------------------------------

(36)
TRUE