971.06/291.46	WORST_CASE(Omega(n^1), ?)
971.06/291.47	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
971.06/291.47	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
971.06/291.47	
971.06/291.47	
971.06/291.47	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
971.06/291.47	
971.06/291.47	(0) CpxTRS
971.06/291.47	(1) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
971.06/291.47	(2) TRS for Loop Detection
971.06/291.47	(3) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
971.06/291.47	(4) BEST
971.06/291.47	    (5) proven lower bound
971.06/291.47	        (6) LowerBoundPropagationProof [FINISHED, 0 ms]
971.06/291.47	        (7) BOUNDS(n^1, INF)
971.06/291.47	    (8) TRS for Loop Detection
971.06/291.47	
971.06/291.47	
971.06/291.47	----------------------------------------
971.06/291.47	
971.06/291.47	(0)
971.06/291.47	Obligation:
971.06/291.47	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
971.06/291.47	
971.06/291.47	
971.06/291.47	The TRS R consists of the following rules:
971.06/291.47	
971.06/291.47	   int(0, 0) -> .(0, nil)
971.06/291.47	   int(0, s(y)) -> .(0, int(s(0), s(y)))
971.06/291.47	   int(s(x), 0) -> nil
971.06/291.47	   int(s(x), s(y)) -> int_list(int(x, y))
971.06/291.47	   int_list(nil) -> nil
971.06/291.47	   int_list(.(x, y)) -> .(s(x), int_list(y))
971.06/291.47	
971.06/291.47	S is empty.
971.06/291.47	Rewrite Strategy: INNERMOST
971.06/291.47	----------------------------------------
971.06/291.47	
971.06/291.47	(1) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
971.06/291.47	Transformed a relative TRS into a decreasing-loop problem.
971.06/291.47	----------------------------------------
971.06/291.47	
971.06/291.47	(2)
971.06/291.47	Obligation:
971.06/291.47	Analyzing the following TRS for decreasing loops:
971.06/291.47	
971.06/291.47	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
971.06/291.47	
971.06/291.47	
971.06/291.47	The TRS R consists of the following rules:
971.06/291.47	
971.06/291.47	   int(0, 0) -> .(0, nil)
971.06/291.47	   int(0, s(y)) -> .(0, int(s(0), s(y)))
971.06/291.47	   int(s(x), 0) -> nil
971.06/291.47	   int(s(x), s(y)) -> int_list(int(x, y))
971.06/291.47	   int_list(nil) -> nil
971.06/291.47	   int_list(.(x, y)) -> .(s(x), int_list(y))
971.06/291.47	
971.06/291.47	S is empty.
971.06/291.47	Rewrite Strategy: INNERMOST
971.06/291.47	----------------------------------------
971.06/291.47	
971.06/291.47	(3) DecreasingLoopProof (LOWER BOUND(ID))
971.06/291.47	The following loop(s) give(s) rise to the lower bound Omega(n^1):
971.06/291.47	
971.06/291.47	The rewrite sequence
971.06/291.47	
971.06/291.47	int_list(.(x, y)) ->^+ .(s(x), int_list(y))
971.06/291.47	
971.06/291.47	gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
971.06/291.47	
971.06/291.47	The pumping substitution is [y / .(x, y)].
971.06/291.47	
971.06/291.47	The result substitution is [ ].
971.06/291.47	
971.06/291.47	
971.06/291.47	
971.06/291.47	
971.06/291.47	----------------------------------------
971.06/291.47	
971.06/291.47	(4)
971.06/291.47	Complex Obligation (BEST)
971.06/291.47	
971.06/291.47	----------------------------------------
971.06/291.47	
971.06/291.47	(5)
971.06/291.47	Obligation:
971.06/291.47	Proved the lower bound n^1 for the following obligation:
971.06/291.47	
971.06/291.47	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
971.06/291.47	
971.06/291.47	
971.06/291.47	The TRS R consists of the following rules:
971.06/291.47	
971.06/291.47	   int(0, 0) -> .(0, nil)
971.06/291.47	   int(0, s(y)) -> .(0, int(s(0), s(y)))
971.06/291.47	   int(s(x), 0) -> nil
971.06/291.47	   int(s(x), s(y)) -> int_list(int(x, y))
971.06/291.47	   int_list(nil) -> nil
971.06/291.47	   int_list(.(x, y)) -> .(s(x), int_list(y))
971.06/291.47	
971.06/291.47	S is empty.
971.06/291.47	Rewrite Strategy: INNERMOST
971.06/291.47	----------------------------------------
971.06/291.47	
971.06/291.47	(6) LowerBoundPropagationProof (FINISHED)
971.06/291.47	Propagated lower bound.
971.06/291.47	----------------------------------------
971.06/291.47	
971.06/291.47	(7)
971.06/291.47	BOUNDS(n^1, INF)
971.06/291.47	
971.06/291.47	----------------------------------------
971.06/291.47	
971.06/291.47	(8)
971.06/291.47	Obligation:
971.06/291.47	Analyzing the following TRS for decreasing loops:
971.06/291.47	
971.06/291.47	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
971.06/291.47	
971.06/291.47	
971.06/291.47	The TRS R consists of the following rules:
971.06/291.47	
971.06/291.47	   int(0, 0) -> .(0, nil)
971.06/291.47	   int(0, s(y)) -> .(0, int(s(0), s(y)))
971.06/291.47	   int(s(x), 0) -> nil
971.06/291.47	   int(s(x), s(y)) -> int_list(int(x, y))
971.06/291.47	   int_list(nil) -> nil
971.06/291.47	   int_list(.(x, y)) -> .(s(x), int_list(y))
971.06/291.47	
971.06/291.47	S is empty.
971.06/291.47	Rewrite Strategy: INNERMOST
971.18/291.52	EOF