305.88/292.30	WORST_CASE(Omega(n^1), ?)
305.88/292.31	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
305.88/292.31	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
305.88/292.31	
305.88/292.31	
305.88/292.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
305.88/292.31	
305.88/292.31	(0) CpxTRS
305.88/292.31	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
305.88/292.31	(2) TRS for Loop Detection
305.88/292.31	(3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
305.88/292.31	(4) BEST
305.88/292.31	    (5) proven lower bound
305.88/292.31	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
305.88/292.31	        (7) BOUNDS(n^1, INF)
305.88/292.31	    (8) TRS for Loop Detection
305.88/292.31	
305.88/292.31	
305.88/292.31	----------------------------------------
305.88/292.31	
305.88/292.31	(0)
305.88/292.31	Obligation:
305.88/292.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
305.88/292.31	
305.88/292.31	
305.88/292.31	The TRS R consists of the following rules:
305.88/292.31	
305.88/292.31	   eq(0, 0) -> true
305.88/292.31	   eq(0, s(x)) -> false
305.88/292.31	   eq(s(x), 0) -> false
305.88/292.31	   eq(s(x), s(y)) -> eq(x, y)
305.88/292.31	   or(true, y) -> true
305.88/292.31	   or(false, y) -> y
305.88/292.31	   union(empty, h) -> h
305.88/292.31	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
305.88/292.31	   reach(x, y, empty, h) -> false
305.88/292.31	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
305.88/292.31	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
305.88/292.31	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
305.88/292.31	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
305.88/292.31	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
305.88/292.31	
305.88/292.31	S is empty.
305.88/292.31	Rewrite Strategy: FULL
305.88/292.31	----------------------------------------
305.88/292.31	
305.88/292.31	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
305.88/292.31	Transformed a relative TRS into a decreasing-loop problem.
305.88/292.31	----------------------------------------
305.88/292.31	
305.88/292.31	(2)
305.88/292.31	Obligation:
305.88/292.31	Analyzing the following TRS for decreasing loops:
305.88/292.31	
305.88/292.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
305.88/292.31	
305.88/292.31	
305.88/292.31	The TRS R consists of the following rules:
305.88/292.31	
305.88/292.31	   eq(0, 0) -> true
305.88/292.31	   eq(0, s(x)) -> false
305.88/292.31	   eq(s(x), 0) -> false
305.88/292.31	   eq(s(x), s(y)) -> eq(x, y)
305.88/292.31	   or(true, y) -> true
305.88/292.31	   or(false, y) -> y
305.88/292.31	   union(empty, h) -> h
305.88/292.31	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
305.88/292.31	   reach(x, y, empty, h) -> false
305.88/292.31	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
305.88/292.31	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
305.88/292.31	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
305.88/292.31	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
305.88/292.31	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
305.88/292.31	
305.88/292.31	S is empty.
305.88/292.31	Rewrite Strategy: FULL
305.88/292.31	----------------------------------------
305.88/292.31	
305.88/292.31	(3) DecreasingLoopProof (LOWER BOUND(ID))
305.88/292.31	The following loop(s) give(s) rise to the lower bound Omega(n^1):
305.88/292.31	
305.88/292.31	The rewrite sequence
305.88/292.31	
305.88/292.31	union(edge(x, y, i), h) ->^+ edge(x, y, union(i, h))
305.88/292.31	
305.88/292.31	gives rise to a decreasing loop by considering the right hand sides subterm at position [2].
305.88/292.31	
305.88/292.31	The pumping substitution is [i / edge(x, y, i)].
305.88/292.31	
305.88/292.31	The result substitution is [ ].
305.88/292.31	
305.88/292.31	
305.88/292.31	
305.88/292.31	
305.88/292.31	----------------------------------------
305.88/292.31	
305.88/292.31	(4)
305.88/292.31	Complex Obligation (BEST)
305.88/292.31	
305.88/292.31	----------------------------------------
305.88/292.31	
305.88/292.31	(5)
305.88/292.31	Obligation:
305.88/292.31	Proved the lower bound n^1 for the following obligation:
305.88/292.31	
305.88/292.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
305.88/292.31	
305.88/292.31	
305.88/292.31	The TRS R consists of the following rules:
305.88/292.31	
305.88/292.31	   eq(0, 0) -> true
305.88/292.31	   eq(0, s(x)) -> false
305.88/292.31	   eq(s(x), 0) -> false
305.88/292.31	   eq(s(x), s(y)) -> eq(x, y)
305.88/292.31	   or(true, y) -> true
305.88/292.31	   or(false, y) -> y
305.88/292.31	   union(empty, h) -> h
305.88/292.31	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
305.88/292.31	   reach(x, y, empty, h) -> false
305.88/292.31	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
305.88/292.31	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
305.88/292.31	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
305.88/292.31	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
305.88/292.31	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
305.88/292.31	
305.88/292.31	S is empty.
305.88/292.31	Rewrite Strategy: FULL
305.88/292.31	----------------------------------------
305.88/292.31	
305.88/292.31	(6) LowerBoundPropagationProof (FINISHED)
305.88/292.31	Propagated lower bound.
305.88/292.31	----------------------------------------
305.88/292.31	
305.88/292.31	(7)
305.88/292.31	BOUNDS(n^1, INF)
305.88/292.31	
305.88/292.31	----------------------------------------
305.88/292.31	
305.88/292.31	(8)
305.88/292.31	Obligation:
305.88/292.31	Analyzing the following TRS for decreasing loops:
305.88/292.31	
305.88/292.31	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
305.88/292.31	
305.88/292.31	
305.88/292.31	The TRS R consists of the following rules:
305.88/292.31	
305.88/292.31	   eq(0, 0) -> true
305.88/292.31	   eq(0, s(x)) -> false
305.88/292.31	   eq(s(x), 0) -> false
305.88/292.31	   eq(s(x), s(y)) -> eq(x, y)
305.88/292.31	   or(true, y) -> true
305.88/292.31	   or(false, y) -> y
305.88/292.31	   union(empty, h) -> h
305.88/292.31	   union(edge(x, y, i), h) -> edge(x, y, union(i, h))
305.88/292.31	   reach(x, y, empty, h) -> false
305.88/292.31	   reach(x, y, edge(u, v, i), h) -> if_reach_1(eq(x, u), x, y, edge(u, v, i), h)
305.88/292.31	   if_reach_1(true, x, y, edge(u, v, i), h) -> if_reach_2(eq(y, v), x, y, edge(u, v, i), h)
305.88/292.31	   if_reach_2(true, x, y, edge(u, v, i), h) -> true
305.88/292.31	   if_reach_2(false, x, y, edge(u, v, i), h) -> or(reach(x, y, i, h), reach(v, y, union(i, h), empty))
305.88/292.31	   if_reach_1(false, x, y, edge(u, v, i), h) -> reach(x, y, i, edge(u, v, h))
305.88/292.31	
305.88/292.31	S is empty.
305.88/292.31	Rewrite Strategy: FULL
305.98/292.33	EOF