324.77/291.52	WORST_CASE(Omega(n^1), ?)
324.77/291.53	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
324.77/291.53	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
324.77/291.53	
324.77/291.53	
324.77/291.53	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
324.77/291.53	
324.77/291.53	(0) CpxTRS
324.77/291.53	(1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
324.77/291.53	(2) CpxTRS
324.77/291.53	(3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
324.77/291.53	(4) typed CpxTrs
324.77/291.53	(5) OrderProof [LOWER BOUND(ID), 0 ms]
324.77/291.53	(6) typed CpxTrs
324.77/291.53	(7) RewriteLemmaProof [LOWER BOUND(ID), 316 ms]
324.77/291.53	(8) BEST
324.77/291.53	    (9) proven lower bound
324.77/291.53	        (10) LowerBoundPropagationProof [FINISHED, 0 ms]
324.77/291.53	        (11) BOUNDS(n^1, INF)
324.77/291.53	    (12) typed CpxTrs
324.77/291.53	
324.77/291.53	
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(0)
324.77/291.53	Obligation:
324.77/291.53	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
324.77/291.53	
324.77/291.53	
324.77/291.53	The TRS R consists of the following rules:
324.77/291.53	
324.77/291.53	   f(X) -> cons(X, n__f(g(X)))
324.77/291.53	   g(0) -> s(0)
324.77/291.53	   g(s(X)) -> s(s(g(X)))
324.77/291.53	   sel(0, cons(X, Y)) -> X
324.77/291.53	   sel(s(X), cons(Y, Z)) -> sel(X, activate(Z))
324.77/291.53	   f(X) -> n__f(X)
324.77/291.53	   activate(n__f(X)) -> f(X)
324.77/291.53	   activate(X) -> X
324.77/291.53	
324.77/291.53	S is empty.
324.77/291.53	Rewrite Strategy: FULL
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(1) RenamingProof (BOTH BOUNDS(ID, ID))
324.77/291.53	Renamed function symbols to avoid clashes with predefined symbol.
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(2)
324.77/291.53	Obligation:
324.77/291.53	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF).
324.77/291.53	
324.77/291.53	
324.77/291.53	The TRS R consists of the following rules:
324.77/291.53	
324.77/291.53	   f(X) -> cons(X, n__f(g(X)))
324.77/291.53	   g(0') -> s(0')
324.77/291.53	   g(s(X)) -> s(s(g(X)))
324.77/291.53	   sel(0', cons(X, Y)) -> X
324.77/291.53	   sel(s(X), cons(Y, Z)) -> sel(X, activate(Z))
324.77/291.53	   f(X) -> n__f(X)
324.77/291.53	   activate(n__f(X)) -> f(X)
324.77/291.53	   activate(X) -> X
324.77/291.53	
324.77/291.53	S is empty.
324.77/291.53	Rewrite Strategy: FULL
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
324.77/291.53	Infered types.
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(4)
324.77/291.53	Obligation:
324.77/291.53	TRS:
324.77/291.53	Rules:
324.77/291.53	f(X) -> cons(X, n__f(g(X)))
324.77/291.53	g(0') -> s(0')
324.77/291.53	g(s(X)) -> s(s(g(X)))
324.77/291.53	sel(0', cons(X, Y)) -> X
324.77/291.53	sel(s(X), cons(Y, Z)) -> sel(X, activate(Z))
324.77/291.53	f(X) -> n__f(X)
324.77/291.53	activate(n__f(X)) -> f(X)
324.77/291.53	activate(X) -> X
324.77/291.53	
324.77/291.53	Types:
324.77/291.53	f :: 0':s -> n__f:cons
324.77/291.53	cons :: 0':s -> n__f:cons -> n__f:cons
324.77/291.53	n__f :: 0':s -> n__f:cons
324.77/291.53	g :: 0':s -> 0':s
324.77/291.53	0' :: 0':s
324.77/291.53	s :: 0':s -> 0':s
324.77/291.53	sel :: 0':s -> n__f:cons -> 0':s
324.77/291.53	activate :: n__f:cons -> n__f:cons
324.77/291.53	hole_n__f:cons1_0 :: n__f:cons
324.77/291.53	hole_0':s2_0 :: 0':s
324.77/291.53	gen_n__f:cons3_0 :: Nat -> n__f:cons
324.77/291.53	gen_0':s4_0 :: Nat -> 0':s
324.77/291.53	
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(5) OrderProof (LOWER BOUND(ID))
324.77/291.53	Heuristically decided to analyse the following defined symbols:
324.77/291.53	g, sel
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(6)
324.77/291.53	Obligation:
324.77/291.53	TRS:
324.77/291.53	Rules:
324.77/291.53	f(X) -> cons(X, n__f(g(X)))
324.77/291.53	g(0') -> s(0')
324.77/291.53	g(s(X)) -> s(s(g(X)))
324.77/291.53	sel(0', cons(X, Y)) -> X
324.77/291.53	sel(s(X), cons(Y, Z)) -> sel(X, activate(Z))
324.77/291.53	f(X) -> n__f(X)
324.77/291.53	activate(n__f(X)) -> f(X)
324.77/291.53	activate(X) -> X
324.77/291.53	
324.77/291.53	Types:
324.77/291.53	f :: 0':s -> n__f:cons
324.77/291.53	cons :: 0':s -> n__f:cons -> n__f:cons
324.77/291.53	n__f :: 0':s -> n__f:cons
324.77/291.53	g :: 0':s -> 0':s
324.77/291.53	0' :: 0':s
324.77/291.53	s :: 0':s -> 0':s
324.77/291.53	sel :: 0':s -> n__f:cons -> 0':s
324.77/291.53	activate :: n__f:cons -> n__f:cons
324.77/291.53	hole_n__f:cons1_0 :: n__f:cons
324.77/291.53	hole_0':s2_0 :: 0':s
324.77/291.53	gen_n__f:cons3_0 :: Nat -> n__f:cons
324.77/291.53	gen_0':s4_0 :: Nat -> 0':s
324.77/291.53	
324.77/291.53	
324.77/291.53	Generator Equations:
324.77/291.53	gen_n__f:cons3_0(0) <=> n__f(0')
324.77/291.53	gen_n__f:cons3_0(+(x, 1)) <=> cons(0', gen_n__f:cons3_0(x))
324.77/291.53	gen_0':s4_0(0) <=> 0'
324.77/291.53	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
324.77/291.53	
324.77/291.53	
324.77/291.53	The following defined symbols remain to be analysed:
324.77/291.53	g, sel
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(7) RewriteLemmaProof (LOWER BOUND(ID))
324.77/291.53	Proved the following rewrite lemma:
324.77/291.53	g(gen_0':s4_0(n6_0)) -> gen_0':s4_0(+(1, *(2, n6_0))), rt in Omega(1 + n6_0)
324.77/291.53	
324.77/291.53	Induction Base:
324.77/291.53	g(gen_0':s4_0(0)) ->_R^Omega(1)
324.77/291.53	s(0')
324.77/291.53	
324.77/291.53	Induction Step:
324.77/291.53	g(gen_0':s4_0(+(n6_0, 1))) ->_R^Omega(1)
324.77/291.53	s(s(g(gen_0':s4_0(n6_0)))) ->_IH
324.77/291.53	s(s(gen_0':s4_0(+(1, *(2, c7_0)))))
324.77/291.53	
324.77/291.53	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(8)
324.77/291.53	Complex Obligation (BEST)
324.77/291.53	
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(9)
324.77/291.53	Obligation:
324.77/291.53	Proved the lower bound n^1 for the following obligation:
324.77/291.53	
324.77/291.53	TRS:
324.77/291.53	Rules:
324.77/291.53	f(X) -> cons(X, n__f(g(X)))
324.77/291.53	g(0') -> s(0')
324.77/291.53	g(s(X)) -> s(s(g(X)))
324.77/291.53	sel(0', cons(X, Y)) -> X
324.77/291.53	sel(s(X), cons(Y, Z)) -> sel(X, activate(Z))
324.77/291.53	f(X) -> n__f(X)
324.77/291.53	activate(n__f(X)) -> f(X)
324.77/291.53	activate(X) -> X
324.77/291.53	
324.77/291.53	Types:
324.77/291.53	f :: 0':s -> n__f:cons
324.77/291.53	cons :: 0':s -> n__f:cons -> n__f:cons
324.77/291.53	n__f :: 0':s -> n__f:cons
324.77/291.53	g :: 0':s -> 0':s
324.77/291.53	0' :: 0':s
324.77/291.53	s :: 0':s -> 0':s
324.77/291.53	sel :: 0':s -> n__f:cons -> 0':s
324.77/291.53	activate :: n__f:cons -> n__f:cons
324.77/291.53	hole_n__f:cons1_0 :: n__f:cons
324.77/291.53	hole_0':s2_0 :: 0':s
324.77/291.53	gen_n__f:cons3_0 :: Nat -> n__f:cons
324.77/291.53	gen_0':s4_0 :: Nat -> 0':s
324.77/291.53	
324.77/291.53	
324.77/291.53	Generator Equations:
324.77/291.53	gen_n__f:cons3_0(0) <=> n__f(0')
324.77/291.53	gen_n__f:cons3_0(+(x, 1)) <=> cons(0', gen_n__f:cons3_0(x))
324.77/291.53	gen_0':s4_0(0) <=> 0'
324.77/291.53	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
324.77/291.53	
324.77/291.53	
324.77/291.53	The following defined symbols remain to be analysed:
324.77/291.53	g, sel
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(10) LowerBoundPropagationProof (FINISHED)
324.77/291.53	Propagated lower bound.
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(11)
324.77/291.53	BOUNDS(n^1, INF)
324.77/291.53	
324.77/291.53	----------------------------------------
324.77/291.53	
324.77/291.53	(12)
324.77/291.53	Obligation:
324.77/291.53	TRS:
324.77/291.53	Rules:
324.77/291.53	f(X) -> cons(X, n__f(g(X)))
324.77/291.53	g(0') -> s(0')
324.77/291.53	g(s(X)) -> s(s(g(X)))
324.77/291.53	sel(0', cons(X, Y)) -> X
324.77/291.53	sel(s(X), cons(Y, Z)) -> sel(X, activate(Z))
324.77/291.53	f(X) -> n__f(X)
324.77/291.53	activate(n__f(X)) -> f(X)
324.77/291.53	activate(X) -> X
324.77/291.53	
324.77/291.53	Types:
324.77/291.53	f :: 0':s -> n__f:cons
324.77/291.53	cons :: 0':s -> n__f:cons -> n__f:cons
324.77/291.53	n__f :: 0':s -> n__f:cons
324.77/291.53	g :: 0':s -> 0':s
324.77/291.53	0' :: 0':s
324.77/291.53	s :: 0':s -> 0':s
324.77/291.53	sel :: 0':s -> n__f:cons -> 0':s
324.77/291.53	activate :: n__f:cons -> n__f:cons
324.77/291.53	hole_n__f:cons1_0 :: n__f:cons
324.77/291.53	hole_0':s2_0 :: 0':s
324.77/291.53	gen_n__f:cons3_0 :: Nat -> n__f:cons
324.77/291.53	gen_0':s4_0 :: Nat -> 0':s
324.77/291.53	
324.77/291.53	
324.77/291.53	Lemmas:
324.77/291.53	g(gen_0':s4_0(n6_0)) -> gen_0':s4_0(+(1, *(2, n6_0))), rt in Omega(1 + n6_0)
324.77/291.53	
324.77/291.53	
324.77/291.53	Generator Equations:
324.77/291.53	gen_n__f:cons3_0(0) <=> n__f(0')
324.77/291.53	gen_n__f:cons3_0(+(x, 1)) <=> cons(0', gen_n__f:cons3_0(x))
324.77/291.53	gen_0':s4_0(0) <=> 0'
324.77/291.53	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
324.77/291.53	
324.77/291.53	
324.77/291.53	The following defined symbols remain to be analysed:
324.77/291.53	sel
324.87/291.56	EOF