1052.90/291.60	WORST_CASE(Omega(n^1), ?)
1052.90/291.63	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
1052.90/291.63	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1052.90/291.63	
1052.90/291.63	(0) CpxTRS
1052.90/291.63	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
1052.90/291.63	(2) CpxTRS
1052.90/291.63	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1052.90/291.63	(4) typed CpxTrs
1052.90/291.63	(5) OrderProof [LOWER BOUND(ID), 0 ms]
1052.90/291.63	(6) typed CpxTrs
1052.90/291.63	(7) RewriteLemmaProof [LOWER BOUND(ID), 284 ms]
1052.90/291.63	(8) BEST
1052.90/291.63	    (9) proven lower bound
1052.90/291.63	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
1052.90/291.63	        (11) BOUNDS(n^1, INF)
1052.90/291.63	    (12) typed CpxTrs
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(0)
1052.90/291.63	Obligation:
1052.90/291.63	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	The TRS R consists of the following rules:
1052.90/291.63	
1052.90/291.63	   a__from(X) -> cons(mark(X), from(s(X)))
1052.90/291.63	   a__length(nil) -> 0
1052.90/291.63	   a__length(cons(X, Y)) -> s(a__length1(Y))
1052.90/291.63	   a__length1(X) -> a__length(X)
1052.90/291.63	   mark(from(X)) -> a__from(mark(X))
1052.90/291.63	   mark(length(X)) -> a__length(X)
1052.90/291.63	   mark(length1(X)) -> a__length1(X)
1052.90/291.63	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
1052.90/291.63	   mark(s(X)) -> s(mark(X))
1052.90/291.63	   mark(nil) -> nil
1052.90/291.63	   mark(0) -> 0
1052.90/291.63	   a__from(X) -> from(X)
1052.90/291.63	   a__length(X) -> length(X)
1052.90/291.63	   a__length1(X) -> length1(X)
1052.90/291.63	
1052.90/291.63	S is empty.
1052.90/291.63	Rewrite Strategy: INNERMOST
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(1) RenamingProof (BOTH BOUNDS(ID, ID))
1052.90/291.63	Renamed function symbols to avoid clashes with predefined symbol.
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(2)
1052.90/291.63	Obligation:
1052.90/291.63	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	The TRS R consists of the following rules:
1052.90/291.63	
1052.90/291.63	   a__from(X) -> cons(mark(X), from(s(X)))
1052.90/291.63	   a__length(nil) -> 0'
1052.90/291.63	   a__length(cons(X, Y)) -> s(a__length1(Y))
1052.90/291.63	   a__length1(X) -> a__length(X)
1052.90/291.63	   mark(from(X)) -> a__from(mark(X))
1052.90/291.63	   mark(length(X)) -> a__length(X)
1052.90/291.63	   mark(length1(X)) -> a__length1(X)
1052.90/291.63	   mark(cons(X1, X2)) -> cons(mark(X1), X2)
1052.90/291.63	   mark(s(X)) -> s(mark(X))
1052.90/291.63	   mark(nil) -> nil
1052.90/291.63	   mark(0') -> 0'
1052.90/291.63	   a__from(X) -> from(X)
1052.90/291.63	   a__length(X) -> length(X)
1052.90/291.63	   a__length1(X) -> length1(X)
1052.90/291.63	
1052.90/291.63	S is empty.
1052.90/291.63	Rewrite Strategy: INNERMOST
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1052.90/291.63	Infered types.
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(4)
1052.90/291.63	Obligation:
1052.90/291.63	Innermost TRS:
1052.90/291.63	Rules:
1052.90/291.63	a__from(X) -> cons(mark(X), from(s(X)))
1052.90/291.63	a__length(nil) -> 0'
1052.90/291.63	a__length(cons(X, Y)) -> s(a__length1(Y))
1052.90/291.63	a__length1(X) -> a__length(X)
1052.90/291.63	mark(from(X)) -> a__from(mark(X))
1052.90/291.63	mark(length(X)) -> a__length(X)
1052.90/291.63	mark(length1(X)) -> a__length1(X)
1052.90/291.63	mark(cons(X1, X2)) -> cons(mark(X1), X2)
1052.90/291.63	mark(s(X)) -> s(mark(X))
1052.90/291.63	mark(nil) -> nil
1052.90/291.63	mark(0') -> 0'
1052.90/291.63	a__from(X) -> from(X)
1052.90/291.63	a__length(X) -> length(X)
1052.90/291.63	a__length1(X) -> length1(X)
1052.90/291.63	
1052.90/291.63	Types:
1052.90/291.63	a__from :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	cons :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	mark :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	from :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	s :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	a__length :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	nil :: s:from:cons:nil:0':length:length1
1052.90/291.63	0' :: s:from:cons:nil:0':length:length1
1052.90/291.63	a__length1 :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	length :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	length1 :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	hole_s:from:cons:nil:0':length:length11_0 :: s:from:cons:nil:0':length:length1
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0 :: Nat -> s:from:cons:nil:0':length:length1
1052.90/291.63	
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(5) OrderProof (LOWER BOUND(ID))
1052.90/291.63	Heuristically decided to analyse the following defined symbols:
1052.90/291.63	a__from, mark, a__length, a__length1
1052.90/291.63	
1052.90/291.63	They will be analysed ascendingly in the following order:
1052.90/291.63	a__from = mark
1052.90/291.63	a__length < mark
1052.90/291.63	a__length1 < mark
1052.90/291.63	a__length = a__length1
1052.90/291.63	
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(6)
1052.90/291.63	Obligation:
1052.90/291.63	Innermost TRS:
1052.90/291.63	Rules:
1052.90/291.63	a__from(X) -> cons(mark(X), from(s(X)))
1052.90/291.63	a__length(nil) -> 0'
1052.90/291.63	a__length(cons(X, Y)) -> s(a__length1(Y))
1052.90/291.63	a__length1(X) -> a__length(X)
1052.90/291.63	mark(from(X)) -> a__from(mark(X))
1052.90/291.63	mark(length(X)) -> a__length(X)
1052.90/291.63	mark(length1(X)) -> a__length1(X)
1052.90/291.63	mark(cons(X1, X2)) -> cons(mark(X1), X2)
1052.90/291.63	mark(s(X)) -> s(mark(X))
1052.90/291.63	mark(nil) -> nil
1052.90/291.63	mark(0') -> 0'
1052.90/291.63	a__from(X) -> from(X)
1052.90/291.63	a__length(X) -> length(X)
1052.90/291.63	a__length1(X) -> length1(X)
1052.90/291.63	
1052.90/291.63	Types:
1052.90/291.63	a__from :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	cons :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	mark :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	from :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	s :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	a__length :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	nil :: s:from:cons:nil:0':length:length1
1052.90/291.63	0' :: s:from:cons:nil:0':length:length1
1052.90/291.63	a__length1 :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	length :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	length1 :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	hole_s:from:cons:nil:0':length:length11_0 :: s:from:cons:nil:0':length:length1
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0 :: Nat -> s:from:cons:nil:0':length:length1
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	Generator Equations:
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0(0) <=> nil
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0(+(x, 1)) <=> cons(gen_s:from:cons:nil:0':length:length12_0(x), nil)
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	The following defined symbols remain to be analysed:
1052.90/291.63	a__length1, a__from, mark, a__length
1052.90/291.63	
1052.90/291.63	They will be analysed ascendingly in the following order:
1052.90/291.63	a__from = mark
1052.90/291.63	a__length < mark
1052.90/291.63	a__length1 < mark
1052.90/291.63	a__length = a__length1
1052.90/291.63	
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(7) RewriteLemmaProof (LOWER BOUND(ID))
1052.90/291.63	Proved the following rewrite lemma:
1052.90/291.63	mark(gen_s:from:cons:nil:0':length:length12_0(n58_0)) -> gen_s:from:cons:nil:0':length:length12_0(n58_0), rt in Omega(1 + n58_0)
1052.90/291.63	
1052.90/291.63	Induction Base:
1052.90/291.63	mark(gen_s:from:cons:nil:0':length:length12_0(0)) ->_R^Omega(1)
1052.90/291.63	nil
1052.90/291.63	
1052.90/291.63	Induction Step:
1052.90/291.63	mark(gen_s:from:cons:nil:0':length:length12_0(+(n58_0, 1))) ->_R^Omega(1)
1052.90/291.63	cons(mark(gen_s:from:cons:nil:0':length:length12_0(n58_0)), nil) ->_IH
1052.90/291.63	cons(gen_s:from:cons:nil:0':length:length12_0(c59_0), nil)
1052.90/291.63	
1052.90/291.63	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(8)
1052.90/291.63	Complex Obligation (BEST)
1052.90/291.63	
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(9)
1052.90/291.63	Obligation:
1052.90/291.63	Proved the lower bound n^1 for the following obligation:
1052.90/291.63	
1052.90/291.63	Innermost TRS:
1052.90/291.63	Rules:
1052.90/291.63	a__from(X) -> cons(mark(X), from(s(X)))
1052.90/291.63	a__length(nil) -> 0'
1052.90/291.63	a__length(cons(X, Y)) -> s(a__length1(Y))
1052.90/291.63	a__length1(X) -> a__length(X)
1052.90/291.63	mark(from(X)) -> a__from(mark(X))
1052.90/291.63	mark(length(X)) -> a__length(X)
1052.90/291.63	mark(length1(X)) -> a__length1(X)
1052.90/291.63	mark(cons(X1, X2)) -> cons(mark(X1), X2)
1052.90/291.63	mark(s(X)) -> s(mark(X))
1052.90/291.63	mark(nil) -> nil
1052.90/291.63	mark(0') -> 0'
1052.90/291.63	a__from(X) -> from(X)
1052.90/291.63	a__length(X) -> length(X)
1052.90/291.63	a__length1(X) -> length1(X)
1052.90/291.63	
1052.90/291.63	Types:
1052.90/291.63	a__from :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	cons :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	mark :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	from :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	s :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	a__length :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	nil :: s:from:cons:nil:0':length:length1
1052.90/291.63	0' :: s:from:cons:nil:0':length:length1
1052.90/291.63	a__length1 :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	length :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	length1 :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	hole_s:from:cons:nil:0':length:length11_0 :: s:from:cons:nil:0':length:length1
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0 :: Nat -> s:from:cons:nil:0':length:length1
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	Generator Equations:
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0(0) <=> nil
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0(+(x, 1)) <=> cons(gen_s:from:cons:nil:0':length:length12_0(x), nil)
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	The following defined symbols remain to be analysed:
1052.90/291.63	mark, a__from
1052.90/291.63	
1052.90/291.63	They will be analysed ascendingly in the following order:
1052.90/291.63	a__from = mark
1052.90/291.63	
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(10) LowerBoundPropagationProof (FINISHED)
1052.90/291.63	Propagated lower bound.
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(11)
1052.90/291.63	BOUNDS(n^1, INF)
1052.90/291.63	
1052.90/291.63	----------------------------------------
1052.90/291.63	
1052.90/291.63	(12)
1052.90/291.63	Obligation:
1052.90/291.63	Innermost TRS:
1052.90/291.63	Rules:
1052.90/291.63	a__from(X) -> cons(mark(X), from(s(X)))
1052.90/291.63	a__length(nil) -> 0'
1052.90/291.63	a__length(cons(X, Y)) -> s(a__length1(Y))
1052.90/291.63	a__length1(X) -> a__length(X)
1052.90/291.63	mark(from(X)) -> a__from(mark(X))
1052.90/291.63	mark(length(X)) -> a__length(X)
1052.90/291.63	mark(length1(X)) -> a__length1(X)
1052.90/291.63	mark(cons(X1, X2)) -> cons(mark(X1), X2)
1052.90/291.63	mark(s(X)) -> s(mark(X))
1052.90/291.63	mark(nil) -> nil
1052.90/291.63	mark(0') -> 0'
1052.90/291.63	a__from(X) -> from(X)
1052.90/291.63	a__length(X) -> length(X)
1052.90/291.63	a__length1(X) -> length1(X)
1052.90/291.63	
1052.90/291.63	Types:
1052.90/291.63	a__from :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	cons :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	mark :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	from :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	s :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	a__length :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	nil :: s:from:cons:nil:0':length:length1
1052.90/291.63	0' :: s:from:cons:nil:0':length:length1
1052.90/291.63	a__length1 :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	length :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	length1 :: s:from:cons:nil:0':length:length1 -> s:from:cons:nil:0':length:length1
1052.90/291.63	hole_s:from:cons:nil:0':length:length11_0 :: s:from:cons:nil:0':length:length1
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0 :: Nat -> s:from:cons:nil:0':length:length1
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	Lemmas:
1052.90/291.63	mark(gen_s:from:cons:nil:0':length:length12_0(n58_0)) -> gen_s:from:cons:nil:0':length:length12_0(n58_0), rt in Omega(1 + n58_0)
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	Generator Equations:
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0(0) <=> nil
1052.90/291.63	gen_s:from:cons:nil:0':length:length12_0(+(x, 1)) <=> cons(gen_s:from:cons:nil:0':length:length12_0(x), nil)
1052.90/291.63	
1052.90/291.63	
1052.90/291.63	The following defined symbols remain to be analysed:
1052.90/291.63	a__from
1052.90/291.63	
1052.90/291.63	They will be analysed ascendingly in the following order:
1052.90/291.63	a__from = mark
1053.42/291.76	EOF