6.94/2.87	YES
6.94/2.88	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
6.94/2.88	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.94/2.88	
6.94/2.88	
6.94/2.88	Termination of the given ETRS could be proven:
6.94/2.88	
6.94/2.88	(0) ETRS
6.94/2.88	(1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms]
6.94/2.88	(2) EDP
6.94/2.88	(3) EDependencyGraphProof [EQUIVALENT, 2 ms]
6.94/2.88	(4) AND
6.94/2.88	    (5) EDP
6.94/2.88	        (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
6.94/2.88	        (7) EDP
6.94/2.88	        (8) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
6.94/2.88	        (9) EDP
6.94/2.88	        (10) PisEmptyProof [EQUIVALENT, 0 ms]
6.94/2.88	        (11) YES
6.94/2.88	    (12) EDP
6.94/2.88	        (13) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
6.94/2.88	        (14) EDP
6.94/2.88	        (15) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
6.94/2.88	        (16) EDP
6.94/2.88	        (17) PisEmptyProof [EQUIVALENT, 0 ms]
6.94/2.88	        (18) YES
6.94/2.88	    (19) EDP
6.94/2.88	        (20) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
6.94/2.88	        (21) EDP
6.94/2.88	        (22) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms]
6.94/2.88	        (23) EDP
6.94/2.88	        (24) PisEmptyProof [EQUIVALENT, 0 ms]
6.94/2.88	        (25) YES
6.94/2.88	    (26) EDP
6.94/2.88	        (27) ESharpUsableEquationsProof [EQUIVALENT, 0 ms]
6.94/2.88	        (28) EDP
6.94/2.88	        (29) EDPPoloProof [EQUIVALENT, 19 ms]
6.94/2.88	        (30) EDP
6.94/2.88	        (31) EDependencyGraphProof [EQUIVALENT, 0 ms]
6.94/2.88	        (32) EDP
6.94/2.88	        (33) EDPPoloProof [EQUIVALENT, 0 ms]
6.94/2.88	        (34) EDP
6.94/2.88	        (35) EDependencyGraphProof [EQUIVALENT, 0 ms]
6.94/2.88	        (36) TRUE
6.94/2.88	
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(0)
6.94/2.88	Obligation:
6.94/2.88	Equational rewrite system:
6.94/2.88	The TRS R consists of the following rules:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.88	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.88	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.88	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	
6.94/2.88	The set E consists of the following equations:
6.94/2.88	
6.94/2.88	   eq(x, y) == eq(y, x)
6.94/2.88	   or(x, y) == or(y, x)
6.94/2.88	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.88	
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(1) EquationalDependencyPairsProof (EQUIVALENT)
6.94/2.88	Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem:
6.94/2.88	The TRS P consists of the following rules:
6.94/2.88	
6.94/2.88	   EQ(s(x), s(y)) -> EQ(x, y)
6.94/2.88	   UNION(edge(x, y, i), h) -> UNION(i, h)
6.94/2.88	   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   REACH(x, y, edge(u, v, i), h) -> EQ(x, u)
6.94/2.88	   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   IF_REACH_1(true, x, y, edge(u, v, i), h) -> EQ(y, v)
6.94/2.88	   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
6.94/2.88	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> OR(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)
6.94/2.88	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
6.94/2.88	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> UNION(i, h)
6.94/2.88	   OR(or(true, y), ext) -> OR(true, ext)
6.94/2.88	
6.94/2.88	The TRS R consists of the following rules:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.88	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.88	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.88	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   or(or(true, y), ext) -> or(true, ext)
6.94/2.88	
6.94/2.88	The set E consists of the following equations:
6.94/2.88	
6.94/2.88	   eq(x, y) == eq(y, x)
6.94/2.88	   or(x, y) == or(y, x)
6.94/2.88	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.88	
6.94/2.88	The set E# consists of the following equations:
6.94/2.88	
6.94/2.88	   EQ(x, y) == EQ(y, x)
6.94/2.88	   OR(x, y) == OR(y, x)
6.94/2.88	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.88	
6.94/2.88	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(2)
6.94/2.88	Obligation:
6.94/2.88	The TRS P consists of the following rules:
6.94/2.88	
6.94/2.88	   EQ(s(x), s(y)) -> EQ(x, y)
6.94/2.88	   UNION(edge(x, y, i), h) -> UNION(i, h)
6.94/2.88	   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   REACH(x, y, edge(u, v, i), h) -> EQ(x, u)
6.94/2.88	   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   IF_REACH_1(true, x, y, edge(u, v, i), h) -> EQ(y, v)
6.94/2.88	   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
6.94/2.88	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> OR(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)
6.94/2.88	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
6.94/2.88	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> UNION(i, h)
6.94/2.88	   OR(or(true, y), ext) -> OR(true, ext)
6.94/2.88	
6.94/2.88	The TRS R consists of the following rules:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.88	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.88	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.88	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   or(or(true, y), ext) -> or(true, ext)
6.94/2.88	
6.94/2.88	The set E consists of the following equations:
6.94/2.88	
6.94/2.88	   eq(x, y) == eq(y, x)
6.94/2.88	   or(x, y) == or(y, x)
6.94/2.88	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.88	
6.94/2.88	The set E# consists of the following equations:
6.94/2.88	
6.94/2.88	   EQ(x, y) == EQ(y, x)
6.94/2.88	   OR(x, y) == OR(y, x)
6.94/2.88	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.88	
6.94/2.88	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(3) EDependencyGraphProof (EQUIVALENT)
6.94/2.88	The approximation of the Equational Dependency Graph [DA_STEIN] contains 4 SCCs with 4 less nodes.
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(4)
6.94/2.88	Complex Obligation (AND)
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(5)
6.94/2.88	Obligation:
6.94/2.88	The TRS P consists of the following rules:
6.94/2.88	
6.94/2.88	   OR(or(true, y), ext) -> OR(true, ext)
6.94/2.88	
6.94/2.88	The TRS R consists of the following rules:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.88	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.88	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.88	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   or(or(true, y), ext) -> or(true, ext)
6.94/2.88	
6.94/2.88	The set E consists of the following equations:
6.94/2.88	
6.94/2.88	   eq(x, y) == eq(y, x)
6.94/2.88	   or(x, y) == or(y, x)
6.94/2.88	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.88	
6.94/2.88	The set E# consists of the following equations:
6.94/2.88	
6.94/2.88	   EQ(x, y) == EQ(y, x)
6.94/2.88	   OR(x, y) == OR(y, x)
6.94/2.88	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.88	
6.94/2.88	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(6) ESharpUsableEquationsProof (EQUIVALENT)
6.94/2.88	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
6.94/2.88	   EQ(x, y) == EQ(y, x)
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(7)
6.94/2.88	Obligation:
6.94/2.88	The TRS P consists of the following rules:
6.94/2.88	
6.94/2.88	   OR(or(true, y), ext) -> OR(true, ext)
6.94/2.88	
6.94/2.88	The TRS R consists of the following rules:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.88	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.88	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.88	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   or(or(true, y), ext) -> or(true, ext)
6.94/2.88	
6.94/2.88	The set E consists of the following equations:
6.94/2.88	
6.94/2.88	   eq(x, y) == eq(y, x)
6.94/2.88	   or(x, y) == or(y, x)
6.94/2.88	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.88	
6.94/2.88	The set E# consists of the following equations:
6.94/2.88	
6.94/2.88	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.88	   OR(x, y) == OR(y, x)
6.94/2.88	
6.94/2.88	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(8) EUsableRulesReductionPairsProof (EQUIVALENT)
6.94/2.88	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.
6.94/2.88	
6.94/2.88	The following dependency pairs can be deleted:
6.94/2.88	
6.94/2.88	   OR(or(true, y), ext) -> OR(true, ext)
6.94/2.88	The following rules are removed from R:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.88	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.88	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.88	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   or(or(true, y), ext) -> or(true, ext)
6.94/2.88	The following equations are removed from E:
6.94/2.88	
6.94/2.88	   eq(x, y) == eq(y, x)
6.94/2.88	Used ordering: POLO with Polynomial interpretation [POLO]:
6.94/2.88	
6.94/2.88	   POL(OR(x_1, x_2)) = 2*x_1 + 2*x_2
6.94/2.88	   POL(false) = 0
6.94/2.88	   POL(or(x_1, x_2)) = 2 + x_1 + x_2
6.94/2.88	   POL(true) = 0
6.94/2.88	
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(9)
6.94/2.88	Obligation:
6.94/2.88	P is empty.
6.94/2.88	R is empty.
6.94/2.88	The set E consists of the following equations:
6.94/2.88	
6.94/2.88	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.88	   or(x, y) == or(y, x)
6.94/2.88	
6.94/2.88	The set E# consists of the following equations:
6.94/2.88	
6.94/2.88	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.88	   OR(x, y) == OR(y, x)
6.94/2.88	
6.94/2.88	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(10) PisEmptyProof (EQUIVALENT)
6.94/2.88	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(11)
6.94/2.88	YES
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(12)
6.94/2.88	Obligation:
6.94/2.88	The TRS P consists of the following rules:
6.94/2.88	
6.94/2.88	   UNION(edge(x, y, i), h) -> UNION(i, h)
6.94/2.88	
6.94/2.88	The TRS R consists of the following rules:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.88	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.88	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.88	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   or(or(true, y), ext) -> or(true, ext)
6.94/2.88	
6.94/2.88	The set E consists of the following equations:
6.94/2.88	
6.94/2.88	   eq(x, y) == eq(y, x)
6.94/2.88	   or(x, y) == or(y, x)
6.94/2.88	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.88	
6.94/2.88	The set E# consists of the following equations:
6.94/2.88	
6.94/2.88	   EQ(x, y) == EQ(y, x)
6.94/2.88	   OR(x, y) == OR(y, x)
6.94/2.88	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.88	
6.94/2.88	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(13) ESharpUsableEquationsProof (EQUIVALENT)
6.94/2.88	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
6.94/2.88	   EQ(x, y) == EQ(y, x)
6.94/2.88	   OR(x, y) == OR(y, x)
6.94/2.88	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(14)
6.94/2.88	Obligation:
6.94/2.88	The TRS P consists of the following rules:
6.94/2.88	
6.94/2.88	   UNION(edge(x, y, i), h) -> UNION(i, h)
6.94/2.88	
6.94/2.88	The TRS R consists of the following rules:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.88	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.88	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.88	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   or(or(true, y), ext) -> or(true, ext)
6.94/2.88	
6.94/2.88	The set E consists of the following equations:
6.94/2.88	
6.94/2.88	   eq(x, y) == eq(y, x)
6.94/2.88	   or(x, y) == or(y, x)
6.94/2.88	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.88	
6.94/2.88	E# is empty.
6.94/2.88	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(15) EUsableRulesReductionPairsProof (EQUIVALENT)
6.94/2.88	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.
6.94/2.88	
6.94/2.88	The following dependency pairs can be deleted:
6.94/2.88	
6.94/2.88	   UNION(edge(x, y, i), h) -> UNION(i, h)
6.94/2.88	The following rules are removed from R:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.88	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.88	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.88	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.88	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.88	   or(or(true, y), ext) -> or(true, ext)
6.94/2.88	The following equations are removed from E:
6.94/2.88	
6.94/2.88	   eq(x, y) == eq(y, x)
6.94/2.88	   or(x, y) == or(y, x)
6.94/2.88	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.88	Used ordering: POLO with Polynomial interpretation [POLO]:
6.94/2.88	
6.94/2.88	   POL(UNION(x_1, x_2)) = 3*x_1 + x_2
6.94/2.88	   POL(edge(x_1, x_2, x_3)) = x_1 + x_2 + 3*x_3
6.94/2.88	
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(16)
6.94/2.88	Obligation:
6.94/2.88	P is empty.
6.94/2.88	R is empty.
6.94/2.88	E is empty.
6.94/2.88	E# is empty.
6.94/2.88	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(17) PisEmptyProof (EQUIVALENT)
6.94/2.88	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(18)
6.94/2.88	YES
6.94/2.88	
6.94/2.88	----------------------------------------
6.94/2.88	
6.94/2.88	(19)
6.94/2.88	Obligation:
6.94/2.88	The TRS P consists of the following rules:
6.94/2.88	
6.94/2.88	   EQ(s(x), s(y)) -> EQ(x, y)
6.94/2.88	
6.94/2.88	The TRS R consists of the following rules:
6.94/2.88	
6.94/2.88	   eq(0, 0) -> true
6.94/2.88	   eq(0, s(x)) -> false
6.94/2.88	   eq(s(x), 0) -> false
6.94/2.88	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.88	   or(true, y) -> true
6.94/2.88	   or(false, y) -> y
6.94/2.88	   union(empty, h) -> h
6.94/2.88	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.88	   reach(x, y, empty, h) -> false
6.94/2.89	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.89	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.89	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.89	   or(or(true, y), ext) -> or(true, ext)
6.94/2.89	
6.94/2.89	The set E consists of the following equations:
6.94/2.89	
6.94/2.89	   eq(x, y) == eq(y, x)
6.94/2.89	   or(x, y) == or(y, x)
6.94/2.89	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.89	
6.94/2.89	The set E# consists of the following equations:
6.94/2.89	
6.94/2.89	   EQ(x, y) == EQ(y, x)
6.94/2.89	   OR(x, y) == OR(y, x)
6.94/2.89	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.89	
6.94/2.89	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(20) ESharpUsableEquationsProof (EQUIVALENT)
6.94/2.89	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
6.94/2.89	   OR(x, y) == OR(y, x)
6.94/2.89	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.89	
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(21)
6.94/2.89	Obligation:
6.94/2.89	The TRS P consists of the following rules:
6.94/2.89	
6.94/2.89	   EQ(s(x), s(y)) -> EQ(x, y)
6.94/2.89	
6.94/2.89	The TRS R consists of the following rules:
6.94/2.89	
6.94/2.89	   eq(0, 0) -> true
6.94/2.89	   eq(0, s(x)) -> false
6.94/2.89	   eq(s(x), 0) -> false
6.94/2.89	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.89	   or(true, y) -> true
6.94/2.89	   or(false, y) -> y
6.94/2.89	   union(empty, h) -> h
6.94/2.89	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.89	   reach(x, y, empty, h) -> false
6.94/2.89	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.89	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.89	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.89	   or(or(true, y), ext) -> or(true, ext)
6.94/2.89	
6.94/2.89	The set E consists of the following equations:
6.94/2.89	
6.94/2.89	   eq(x, y) == eq(y, x)
6.94/2.89	   or(x, y) == or(y, x)
6.94/2.89	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.89	
6.94/2.89	The set E# consists of the following equations:
6.94/2.89	
6.94/2.89	   EQ(x, y) == EQ(y, x)
6.94/2.89	
6.94/2.89	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(22) EUsableRulesReductionPairsProof (EQUIVALENT)
6.94/2.89	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.
6.94/2.89	
6.94/2.89	The following dependency pairs can be deleted:
6.94/2.89	
6.94/2.89	   EQ(s(x), s(y)) -> EQ(x, y)
6.94/2.89	The following rules are removed from R:
6.94/2.89	
6.94/2.89	   eq(0, 0) -> true
6.94/2.89	   eq(0, s(x)) -> false
6.94/2.89	   eq(s(x), 0) -> false
6.94/2.89	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.89	   or(true, y) -> true
6.94/2.89	   or(false, y) -> y
6.94/2.89	   union(empty, h) -> h
6.94/2.89	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.89	   reach(x, y, empty, h) -> false
6.94/2.89	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.89	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.89	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.89	   or(or(true, y), ext) -> or(true, ext)
6.94/2.89	The following equations are removed from E:
6.94/2.89	
6.94/2.89	   eq(x, y) == eq(y, x)
6.94/2.89	   or(x, y) == or(y, x)
6.94/2.89	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.89	Used ordering: POLO with Polynomial interpretation [POLO]:
6.94/2.89	
6.94/2.89	   POL(EQ(x_1, x_2)) = 3*x_1 + 3*x_2
6.94/2.89	   POL(s(x_1)) = 3*x_1
6.94/2.89	
6.94/2.89	
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(23)
6.94/2.89	Obligation:
6.94/2.89	P is empty.
6.94/2.89	R is empty.
6.94/2.89	E is empty.
6.94/2.89	The set E# consists of the following equations:
6.94/2.89	
6.94/2.89	   EQ(x, y) == EQ(y, x)
6.94/2.89	
6.94/2.89	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(24) PisEmptyProof (EQUIVALENT)
6.94/2.89	The TRS P is empty. Hence, there is no (P,E#,R,E) chain.
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(25)
6.94/2.89	YES
6.94/2.89	
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(26)
6.94/2.89	Obligation:
6.94/2.89	The TRS P consists of the following rules:
6.94/2.89	
6.94/2.89	   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
6.94/2.89	   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
6.94/2.89	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)
6.94/2.89	
6.94/2.89	The TRS R consists of the following rules:
6.94/2.89	
6.94/2.89	   eq(0, 0) -> true
6.94/2.89	   eq(0, s(x)) -> false
6.94/2.89	   eq(s(x), 0) -> false
6.94/2.89	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.89	   or(true, y) -> true
6.94/2.89	   or(false, y) -> y
6.94/2.89	   union(empty, h) -> h
6.94/2.89	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.89	   reach(x, y, empty, h) -> false
6.94/2.89	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.89	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.89	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.89	   or(or(true, y), ext) -> or(true, ext)
6.94/2.89	
6.94/2.89	The set E consists of the following equations:
6.94/2.89	
6.94/2.89	   eq(x, y) == eq(y, x)
6.94/2.89	   or(x, y) == or(y, x)
6.94/2.89	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.89	
6.94/2.89	The set E# consists of the following equations:
6.94/2.89	
6.94/2.89	   EQ(x, y) == EQ(y, x)
6.94/2.89	   OR(x, y) == OR(y, x)
6.94/2.89	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.89	
6.94/2.89	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(27) ESharpUsableEquationsProof (EQUIVALENT)
6.94/2.89	We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]:
6.94/2.89	   EQ(x, y) == EQ(y, x)
6.94/2.89	   OR(x, y) == OR(y, x)
6.94/2.89	   OR(or(x, y), z) == OR(x, or(y, z))
6.94/2.89	
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(28)
6.94/2.89	Obligation:
6.94/2.89	The TRS P consists of the following rules:
6.94/2.89	
6.94/2.89	   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
6.94/2.89	   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
6.94/2.89	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)
6.94/2.89	
6.94/2.89	The TRS R consists of the following rules:
6.94/2.89	
6.94/2.89	   eq(0, 0) -> true
6.94/2.89	   eq(0, s(x)) -> false
6.94/2.89	   eq(s(x), 0) -> false
6.94/2.89	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.89	   or(true, y) -> true
6.94/2.89	   or(false, y) -> y
6.94/2.89	   union(empty, h) -> h
6.94/2.89	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.89	   reach(x, y, empty, h) -> false
6.94/2.89	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.89	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.89	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.89	   or(or(true, y), ext) -> or(true, ext)
6.94/2.89	
6.94/2.89	The set E consists of the following equations:
6.94/2.89	
6.94/2.89	   eq(x, y) == eq(y, x)
6.94/2.89	   or(x, y) == or(y, x)
6.94/2.89	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.89	
6.94/2.89	E# is empty.
6.94/2.89	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(29) EDPPoloProof (EQUIVALENT)
6.94/2.89	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.
6.94/2.89	
6.94/2.89	
6.94/2.89	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(v, y, union(i, h), empty)
6.94/2.89	   IF_REACH_2(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, h)
6.94/2.89	The remaining Dependency Pairs were at least non-strictly oriented.
6.94/2.89	
6.94/2.89	
6.94/2.89	   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
6.94/2.89	With the implicit AFS we had to orient the following set of usable rules of R non-strictly.
6.94/2.89	
6.94/2.89	
6.94/2.89	   union(empty, h) -> h
6.94/2.89	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.89	There is no equation of E#.
6.94/2.89	
6.94/2.89	
6.94/2.89	With the implicit AFS there is no usable equation of E.
6.94/2.89	
6.94/2.89	
6.94/2.89	Used ordering: POLO with Polynomial interpretation [POLO]:
6.94/2.89	
6.94/2.89	   POL(0) = 0
6.94/2.89	   POL(IF_REACH_1(x_1, x_2, x_3, x_4, x_5)) = 3*x_3 + 2*x_4 + 2*x_5
6.94/2.89	   POL(IF_REACH_2(x_1, x_2, x_3, x_4, x_5)) = 3*x_3 + 2*x_4 + 2*x_5
6.94/2.89	   POL(REACH(x_1, x_2, x_3, x_4)) = 3*x_2 + 2*x_3 + 2*x_4
6.94/2.89	   POL(edge(x_1, x_2, x_3)) = 1 + x_3
6.94/2.89	   POL(empty) = 0
6.94/2.89	   POL(eq(x_1, x_2)) = 0
6.94/2.89	   POL(false) = 0
6.94/2.89	   POL(s(x_1)) = 0
6.94/2.89	   POL(true) = 0
6.94/2.89	   POL(union(x_1, x_2)) = x_1 + x_2
6.94/2.89	
6.94/2.89	
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(30)
6.94/2.89	Obligation:
6.94/2.89	The TRS P consists of the following rules:
6.94/2.89	
6.94/2.89	   IF_REACH_1(true, x, y, edge(u, v, i), h) -> IF_REACH_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
6.94/2.89	
6.94/2.89	The TRS R consists of the following rules:
6.94/2.89	
6.94/2.89	   eq(0, 0) -> true
6.94/2.89	   eq(0, s(x)) -> false
6.94/2.89	   eq(s(x), 0) -> false
6.94/2.89	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.89	   or(true, y) -> true
6.94/2.89	   or(false, y) -> y
6.94/2.89	   union(empty, h) -> h
6.94/2.89	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.89	   reach(x, y, empty, h) -> false
6.94/2.89	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.89	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.89	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.89	   or(or(true, y), ext) -> or(true, ext)
6.94/2.89	
6.94/2.89	The set E consists of the following equations:
6.94/2.89	
6.94/2.89	   eq(x, y) == eq(y, x)
6.94/2.89	   or(x, y) == or(y, x)
6.94/2.89	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.89	
6.94/2.89	E# is empty.
6.94/2.89	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(31) EDependencyGraphProof (EQUIVALENT)
6.94/2.89	The approximation of the Equational Dependency Graph [DA_STEIN] contains 1 SCC with 1 less node.
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(32)
6.94/2.89	Obligation:
6.94/2.89	The TRS P consists of the following rules:
6.94/2.89	
6.94/2.89	   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
6.94/2.89	   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	
6.94/2.89	The TRS R consists of the following rules:
6.94/2.89	
6.94/2.89	   eq(0, 0) -> true
6.94/2.89	   eq(0, s(x)) -> false
6.94/2.89	   eq(s(x), 0) -> false
6.94/2.89	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.89	   or(true, y) -> true
6.94/2.89	   or(false, y) -> y
6.94/2.89	   union(empty, h) -> h
6.94/2.89	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.89	   reach(x, y, empty, h) -> false
6.94/2.89	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.89	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.89	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.89	   or(or(true, y), ext) -> or(true, ext)
6.94/2.89	
6.94/2.89	The set E consists of the following equations:
6.94/2.89	
6.94/2.89	   eq(x, y) == eq(y, x)
6.94/2.89	   or(x, y) == or(y, x)
6.94/2.89	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.89	
6.94/2.89	E# is empty.
6.94/2.89	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(33) EDPPoloProof (EQUIVALENT)
6.94/2.89	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.
6.94/2.89	
6.94/2.89	
6.94/2.89	   REACH(x, y, edge(u, v, i), h) -> IF_REACH_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	The remaining Dependency Pairs were at least non-strictly oriented.
6.94/2.89	
6.94/2.89	
6.94/2.89	   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
6.94/2.89	With the implicit AFS there is no usable rule of R.
6.94/2.89	
6.94/2.89	
6.94/2.89	There is no equation of E#.
6.94/2.89	
6.94/2.89	
6.94/2.89	With the implicit AFS there is no usable equation of E.
6.94/2.89	
6.94/2.89	
6.94/2.89	Used ordering: POLO with Polynomial interpretation [POLO]:
6.94/2.89	
6.94/2.89	   POL(0) = 0
6.94/2.89	   POL(IF_REACH_1(x_1, x_2, x_3, x_4, x_5)) = 1 + 3*x_2 + x_4
6.94/2.89	   POL(REACH(x_1, x_2, x_3, x_4)) = 2 + 3*x_1 + 3*x_3
6.94/2.89	   POL(edge(x_1, x_2, x_3)) = 1 + 2*x_2 + 3*x_3
6.94/2.89	   POL(eq(x_1, x_2)) = 0
6.94/2.89	   POL(false) = 0
6.94/2.89	   POL(s(x_1)) = 0
6.94/2.89	   POL(true) = 3
6.94/2.89	
6.94/2.89	
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(34)
6.94/2.89	Obligation:
6.94/2.89	The TRS P consists of the following rules:
6.94/2.89	
6.94/2.89	   IF_REACH_1(false, x, y, edge(u, v, i), h) -> REACH(x, y, i, edge(u, v, h))
6.94/2.89	
6.94/2.89	The TRS R consists of the following rules:
6.94/2.89	
6.94/2.89	   eq(0, 0) -> true
6.94/2.89	   eq(0, s(x)) -> false
6.94/2.89	   eq(s(x), 0) -> false
6.94/2.89	   eq(s(x), s(y)) -> eq(x, y)
6.94/2.89	   or(true, y) -> true
6.94/2.89	   or(false, y) -> y
6.94/2.89	   union(empty, h) -> h
6.94/2.89	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
6.94/2.89	   reach(x, y, empty, h) -> false
6.94/2.89	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
6.94/2.89	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
6.94/2.89	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
6.94/2.89	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
6.94/2.89	   or(or(true, y), ext) -> or(true, ext)
6.94/2.89	
6.94/2.89	The set E consists of the following equations:
6.94/2.89	
6.94/2.89	   eq(x, y) == eq(y, x)
6.94/2.89	   or(x, y) == or(y, x)
6.94/2.89	   or(or(x, y), z) == or(x, or(y, z))
6.94/2.89	
6.94/2.89	E# is empty.
6.94/2.89	We have to consider all minimal (P,E#,R,E)-chains
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(35) EDependencyGraphProof (EQUIVALENT)
6.94/2.89	The approximation of the Equational Dependency Graph [DA_STEIN] contains 0 SCCs with 1 less node.
6.94/2.89	----------------------------------------
6.94/2.89	
6.94/2.89	(36)
6.94/2.89	TRUE
7.01/2.92	EOF