867.89/242.79	WORST_CASE(NON_POLY, ?)
867.89/242.79	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
867.89/242.79	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
867.89/242.79	
867.89/242.79	
867.89/242.79	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(INF, INF).
867.89/242.79	
867.89/242.79	(0) CpxRelTRS
867.89/242.79	(1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 367 ms]
867.89/242.79	(2) CpxRelTRS
867.89/242.79	(3) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
867.89/242.79	(4) TRS for Loop Detection
867.89/242.79	(5) DecreasingLoopProof [LOWER BOUND(ID), 83 ms]
867.89/242.79	(6) BEST
867.89/242.79	    (7) proven lower bound
867.89/242.79	        (8) LowerBoundPropagationProof [FINISHED, 0 ms]
867.89/242.79	        (9) BOUNDS(n^1, INF)
867.89/242.79	    (10) TRS for Loop Detection
867.89/242.79	        (11) InfiniteLowerBoundProof [FINISHED, 158.1 s]
867.89/242.79	        (12) BOUNDS(INF, INF)
867.89/242.79	
867.89/242.79	
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(0)
867.89/242.79	Obligation:
867.89/242.79	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(INF, INF).
867.89/242.79	
867.89/242.79	
867.89/242.79	The TRS R consists of the following rules:
867.89/242.79	
867.89/242.79	   getNodeFromEdge(S(S(x')), E(x, y)) -> y
867.89/242.79	   via(u, v, Cons(E(x, y), xs), edges) -> via[Ite](!EQ(u, x), u, v, Cons(E(x, y), xs), edges)
867.89/242.79	   getNodeFromEdge(S(0), E(x, y)) -> x
867.89/242.79	   member(x', Cons(x, xs)) -> member[Ite](eqEdge(x', x), x', Cons(x, xs))
867.89/242.79	   getNodeFromEdge(0, E(x, y)) -> x
867.89/242.79	   eqEdge(E(e11, e12), E(e21, e22)) -> eqEdge[Ite](and(!EQ(e11, e21), !EQ(e12, e22)), e21, e22, e11, e12)
867.89/242.79	   via(u, v, Nil, edges) -> Nil
867.89/242.79	   notEmpty(Cons(x, xs)) -> True
867.89/242.79	   notEmpty(Nil) -> False
867.89/242.79	   member(x, Nil) -> False
867.89/242.79	   reach(u, v, edges) -> reach[Ite](member(E(u, v), edges), u, v, edges)
867.89/242.79	   goal(u, v, edges) -> reach(u, v, edges)
867.89/242.79	
867.89/242.79	The (relative) TRS S consists of the following rules:
867.89/242.79	
867.89/242.79	   !EQ(S(x), S(y)) -> !EQ(x, y)
867.89/242.79	   !EQ(0, S(y)) -> False
867.89/242.79	   !EQ(S(x), 0) -> False
867.89/242.79	   !EQ(0, 0) -> True
867.89/242.79	   and(False, False) -> False
867.89/242.79	   and(True, False) -> False
867.89/242.79	   and(False, True) -> False
867.89/242.79	   and(True, True) -> True
867.89/242.79	   via[Ite](True, u, v, Cons(E(x, y), xs), edges) -> via[Let](u, v, Cons(E(x, y), xs), edges, reach(y, v, edges))
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Nil) -> via(u, v, xs, edges)
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Cons(x', xs')) -> Cons(x, Cons(x', xs'))
867.89/242.79	   via[Ite](False, u, v, Cons(x, xs), edges) -> via(u, v, xs, edges)
867.89/242.79	   member[Ite](False, x', Cons(x, xs)) -> member(x', xs)
867.89/242.79	   reach[Ite](False, u, v, edges) -> via(u, v, edges, edges)
867.89/242.79	   reach[Ite](True, u, v, edges) -> Cons(E(u, v), Nil)
867.89/242.79	   member[Ite](True, x, xs) -> True
867.89/242.79	   eqEdge[Ite](False, e21, e22, e11, e12) -> False
867.89/242.79	   eqEdge[Ite](True, e21, e22, e11, e12) -> True
867.89/242.79	
867.89/242.79	Rewrite Strategy: INNERMOST
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID))
867.89/242.79	proved termination of relative rules
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(2)
867.89/242.79	Obligation:
867.89/242.79	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(INF, INF).
867.89/242.79	
867.89/242.79	
867.89/242.79	The TRS R consists of the following rules:
867.89/242.79	
867.89/242.79	   getNodeFromEdge(S(S(x')), E(x, y)) -> y
867.89/242.79	   via(u, v, Cons(E(x, y), xs), edges) -> via[Ite](!EQ(u, x), u, v, Cons(E(x, y), xs), edges)
867.89/242.79	   getNodeFromEdge(S(0), E(x, y)) -> x
867.89/242.79	   member(x', Cons(x, xs)) -> member[Ite](eqEdge(x', x), x', Cons(x, xs))
867.89/242.79	   getNodeFromEdge(0, E(x, y)) -> x
867.89/242.79	   eqEdge(E(e11, e12), E(e21, e22)) -> eqEdge[Ite](and(!EQ(e11, e21), !EQ(e12, e22)), e21, e22, e11, e12)
867.89/242.79	   via(u, v, Nil, edges) -> Nil
867.89/242.79	   notEmpty(Cons(x, xs)) -> True
867.89/242.79	   notEmpty(Nil) -> False
867.89/242.79	   member(x, Nil) -> False
867.89/242.79	   reach(u, v, edges) -> reach[Ite](member(E(u, v), edges), u, v, edges)
867.89/242.79	   goal(u, v, edges) -> reach(u, v, edges)
867.89/242.79	
867.89/242.79	The (relative) TRS S consists of the following rules:
867.89/242.79	
867.89/242.79	   !EQ(S(x), S(y)) -> !EQ(x, y)
867.89/242.79	   !EQ(0, S(y)) -> False
867.89/242.79	   !EQ(S(x), 0) -> False
867.89/242.79	   !EQ(0, 0) -> True
867.89/242.79	   and(False, False) -> False
867.89/242.79	   and(True, False) -> False
867.89/242.79	   and(False, True) -> False
867.89/242.79	   and(True, True) -> True
867.89/242.79	   via[Ite](True, u, v, Cons(E(x, y), xs), edges) -> via[Let](u, v, Cons(E(x, y), xs), edges, reach(y, v, edges))
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Nil) -> via(u, v, xs, edges)
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Cons(x', xs')) -> Cons(x, Cons(x', xs'))
867.89/242.79	   via[Ite](False, u, v, Cons(x, xs), edges) -> via(u, v, xs, edges)
867.89/242.79	   member[Ite](False, x', Cons(x, xs)) -> member(x', xs)
867.89/242.79	   reach[Ite](False, u, v, edges) -> via(u, v, edges, edges)
867.89/242.79	   reach[Ite](True, u, v, edges) -> Cons(E(u, v), Nil)
867.89/242.79	   member[Ite](True, x, xs) -> True
867.89/242.79	   eqEdge[Ite](False, e21, e22, e11, e12) -> False
867.89/242.79	   eqEdge[Ite](True, e21, e22, e11, e12) -> True
867.89/242.79	
867.89/242.79	Rewrite Strategy: INNERMOST
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(3) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
867.89/242.79	Transformed a relative TRS into a decreasing-loop problem.
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(4)
867.89/242.79	Obligation:
867.89/242.79	Analyzing the following TRS for decreasing loops:
867.89/242.79	
867.89/242.79	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(INF, INF).
867.89/242.79	
867.89/242.79	
867.89/242.79	The TRS R consists of the following rules:
867.89/242.79	
867.89/242.79	   getNodeFromEdge(S(S(x')), E(x, y)) -> y
867.89/242.79	   via(u, v, Cons(E(x, y), xs), edges) -> via[Ite](!EQ(u, x), u, v, Cons(E(x, y), xs), edges)
867.89/242.79	   getNodeFromEdge(S(0), E(x, y)) -> x
867.89/242.79	   member(x', Cons(x, xs)) -> member[Ite](eqEdge(x', x), x', Cons(x, xs))
867.89/242.79	   getNodeFromEdge(0, E(x, y)) -> x
867.89/242.79	   eqEdge(E(e11, e12), E(e21, e22)) -> eqEdge[Ite](and(!EQ(e11, e21), !EQ(e12, e22)), e21, e22, e11, e12)
867.89/242.79	   via(u, v, Nil, edges) -> Nil
867.89/242.79	   notEmpty(Cons(x, xs)) -> True
867.89/242.79	   notEmpty(Nil) -> False
867.89/242.79	   member(x, Nil) -> False
867.89/242.79	   reach(u, v, edges) -> reach[Ite](member(E(u, v), edges), u, v, edges)
867.89/242.79	   goal(u, v, edges) -> reach(u, v, edges)
867.89/242.79	
867.89/242.79	The (relative) TRS S consists of the following rules:
867.89/242.79	
867.89/242.79	   !EQ(S(x), S(y)) -> !EQ(x, y)
867.89/242.79	   !EQ(0, S(y)) -> False
867.89/242.79	   !EQ(S(x), 0) -> False
867.89/242.79	   !EQ(0, 0) -> True
867.89/242.79	   and(False, False) -> False
867.89/242.79	   and(True, False) -> False
867.89/242.79	   and(False, True) -> False
867.89/242.79	   and(True, True) -> True
867.89/242.79	   via[Ite](True, u, v, Cons(E(x, y), xs), edges) -> via[Let](u, v, Cons(E(x, y), xs), edges, reach(y, v, edges))
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Nil) -> via(u, v, xs, edges)
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Cons(x', xs')) -> Cons(x, Cons(x', xs'))
867.89/242.79	   via[Ite](False, u, v, Cons(x, xs), edges) -> via(u, v, xs, edges)
867.89/242.79	   member[Ite](False, x', Cons(x, xs)) -> member(x', xs)
867.89/242.79	   reach[Ite](False, u, v, edges) -> via(u, v, edges, edges)
867.89/242.79	   reach[Ite](True, u, v, edges) -> Cons(E(u, v), Nil)
867.89/242.79	   member[Ite](True, x, xs) -> True
867.89/242.79	   eqEdge[Ite](False, e21, e22, e11, e12) -> False
867.89/242.79	   eqEdge[Ite](True, e21, e22, e11, e12) -> True
867.89/242.79	
867.89/242.79	Rewrite Strategy: INNERMOST
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(5) DecreasingLoopProof (LOWER BOUND(ID))
867.89/242.79	The following loop(s) give(s) rise to the lower bound Omega(n^1):
867.89/242.79	
867.89/242.79	The rewrite sequence
867.89/242.79	
867.89/242.79	via(0, v, Cons(E(S(y1_0), y), xs), edges) ->^+ via(0, v, xs, edges)
867.89/242.79	
867.89/242.79	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
867.89/242.79	
867.89/242.79	The pumping substitution is [xs / Cons(E(S(y1_0), y), xs)].
867.89/242.79	
867.89/242.79	The result substitution is [ ].
867.89/242.79	
867.89/242.79	
867.89/242.79	
867.89/242.79	
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(6)
867.89/242.79	Complex Obligation (BEST)
867.89/242.79	
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(7)
867.89/242.79	Obligation:
867.89/242.79	Proved the lower bound n^1 for the following obligation:
867.89/242.79	
867.89/242.79	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(INF, INF).
867.89/242.79	
867.89/242.79	
867.89/242.79	The TRS R consists of the following rules:
867.89/242.79	
867.89/242.79	   getNodeFromEdge(S(S(x')), E(x, y)) -> y
867.89/242.79	   via(u, v, Cons(E(x, y), xs), edges) -> via[Ite](!EQ(u, x), u, v, Cons(E(x, y), xs), edges)
867.89/242.79	   getNodeFromEdge(S(0), E(x, y)) -> x
867.89/242.79	   member(x', Cons(x, xs)) -> member[Ite](eqEdge(x', x), x', Cons(x, xs))
867.89/242.79	   getNodeFromEdge(0, E(x, y)) -> x
867.89/242.79	   eqEdge(E(e11, e12), E(e21, e22)) -> eqEdge[Ite](and(!EQ(e11, e21), !EQ(e12, e22)), e21, e22, e11, e12)
867.89/242.79	   via(u, v, Nil, edges) -> Nil
867.89/242.79	   notEmpty(Cons(x, xs)) -> True
867.89/242.79	   notEmpty(Nil) -> False
867.89/242.79	   member(x, Nil) -> False
867.89/242.79	   reach(u, v, edges) -> reach[Ite](member(E(u, v), edges), u, v, edges)
867.89/242.79	   goal(u, v, edges) -> reach(u, v, edges)
867.89/242.79	
867.89/242.79	The (relative) TRS S consists of the following rules:
867.89/242.79	
867.89/242.79	   !EQ(S(x), S(y)) -> !EQ(x, y)
867.89/242.79	   !EQ(0, S(y)) -> False
867.89/242.79	   !EQ(S(x), 0) -> False
867.89/242.79	   !EQ(0, 0) -> True
867.89/242.79	   and(False, False) -> False
867.89/242.79	   and(True, False) -> False
867.89/242.79	   and(False, True) -> False
867.89/242.79	   and(True, True) -> True
867.89/242.79	   via[Ite](True, u, v, Cons(E(x, y), xs), edges) -> via[Let](u, v, Cons(E(x, y), xs), edges, reach(y, v, edges))
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Nil) -> via(u, v, xs, edges)
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Cons(x', xs')) -> Cons(x, Cons(x', xs'))
867.89/242.79	   via[Ite](False, u, v, Cons(x, xs), edges) -> via(u, v, xs, edges)
867.89/242.79	   member[Ite](False, x', Cons(x, xs)) -> member(x', xs)
867.89/242.79	   reach[Ite](False, u, v, edges) -> via(u, v, edges, edges)
867.89/242.79	   reach[Ite](True, u, v, edges) -> Cons(E(u, v), Nil)
867.89/242.79	   member[Ite](True, x, xs) -> True
867.89/242.79	   eqEdge[Ite](False, e21, e22, e11, e12) -> False
867.89/242.79	   eqEdge[Ite](True, e21, e22, e11, e12) -> True
867.89/242.79	
867.89/242.79	Rewrite Strategy: INNERMOST
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(8) LowerBoundPropagationProof (FINISHED)
867.89/242.79	Propagated lower bound.
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(9)
867.89/242.79	BOUNDS(n^1, INF)
867.89/242.79	
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(10)
867.89/242.79	Obligation:
867.89/242.79	Analyzing the following TRS for decreasing loops:
867.89/242.79	
867.89/242.79	The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(INF, INF).
867.89/242.79	
867.89/242.79	
867.89/242.79	The TRS R consists of the following rules:
867.89/242.79	
867.89/242.79	   getNodeFromEdge(S(S(x')), E(x, y)) -> y
867.89/242.79	   via(u, v, Cons(E(x, y), xs), edges) -> via[Ite](!EQ(u, x), u, v, Cons(E(x, y), xs), edges)
867.89/242.79	   getNodeFromEdge(S(0), E(x, y)) -> x
867.89/242.79	   member(x', Cons(x, xs)) -> member[Ite](eqEdge(x', x), x', Cons(x, xs))
867.89/242.79	   getNodeFromEdge(0, E(x, y)) -> x
867.89/242.79	   eqEdge(E(e11, e12), E(e21, e22)) -> eqEdge[Ite](and(!EQ(e11, e21), !EQ(e12, e22)), e21, e22, e11, e12)
867.89/242.79	   via(u, v, Nil, edges) -> Nil
867.89/242.79	   notEmpty(Cons(x, xs)) -> True
867.89/242.79	   notEmpty(Nil) -> False
867.89/242.79	   member(x, Nil) -> False
867.89/242.79	   reach(u, v, edges) -> reach[Ite](member(E(u, v), edges), u, v, edges)
867.89/242.79	   goal(u, v, edges) -> reach(u, v, edges)
867.89/242.79	
867.89/242.79	The (relative) TRS S consists of the following rules:
867.89/242.79	
867.89/242.79	   !EQ(S(x), S(y)) -> !EQ(x, y)
867.89/242.79	   !EQ(0, S(y)) -> False
867.89/242.79	   !EQ(S(x), 0) -> False
867.89/242.79	   !EQ(0, 0) -> True
867.89/242.79	   and(False, False) -> False
867.89/242.79	   and(True, False) -> False
867.89/242.79	   and(False, True) -> False
867.89/242.79	   and(True, True) -> True
867.89/242.79	   via[Ite](True, u, v, Cons(E(x, y), xs), edges) -> via[Let](u, v, Cons(E(x, y), xs), edges, reach(y, v, edges))
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Nil) -> via(u, v, xs, edges)
867.89/242.79	   via[Let](u, v, Cons(x, xs), edges, Cons(x', xs')) -> Cons(x, Cons(x', xs'))
867.89/242.79	   via[Ite](False, u, v, Cons(x, xs), edges) -> via(u, v, xs, edges)
867.89/242.79	   member[Ite](False, x', Cons(x, xs)) -> member(x', xs)
867.89/242.79	   reach[Ite](False, u, v, edges) -> via(u, v, edges, edges)
867.89/242.79	   reach[Ite](True, u, v, edges) -> Cons(E(u, v), Nil)
867.89/242.79	   member[Ite](True, x, xs) -> True
867.89/242.79	   eqEdge[Ite](False, e21, e22, e11, e12) -> False
867.89/242.79	   eqEdge[Ite](True, e21, e22, e11, e12) -> True
867.89/242.79	
867.89/242.79	Rewrite Strategy: INNERMOST
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(11) InfiniteLowerBoundProof (FINISHED)
867.89/242.79	The following loop proves infinite runtime complexity:
867.89/242.79	
867.89/242.79	The rewrite sequence
867.89/242.79	
867.89/242.79	reach(0, S(x1_2), Cons(E(0, 0), Nil)) ->^+ via[Let](0, S(x1_2), Cons(E(0, 0), Nil), Cons(E(0, 0), Nil), reach(0, S(x1_2), Cons(E(0, 0), Nil)))
867.89/242.79	
867.89/242.79	gives rise to a decreasing loop by considering the right hand sides subterm at position [4].
867.89/242.79	
867.89/242.79	The pumping substitution is [ ].
867.89/242.79	
867.89/242.79	The result substitution is [ ].
867.89/242.79	
867.89/242.79	
867.89/242.79	
867.89/242.79	
867.89/242.79	----------------------------------------
867.89/242.79	
867.89/242.79	(12)
867.89/242.79	BOUNDS(INF, INF)
868.16/242.91	EOF