11.71/3.82	WORST_CASE(Omega(n^2), O(n^2))
11.88/3.83	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
11.88/3.83	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
11.88/3.83	
11.88/3.83	
11.88/3.83	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2).
11.88/3.83	
11.88/3.83	(0) CpxTRS
11.88/3.83	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
11.88/3.83	(2) CpxWeightedTrs
11.88/3.83	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
11.88/3.83	    (4) CpxTypedWeightedTrs
11.88/3.83	    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
11.88/3.83	    (6) CpxTypedWeightedCompleteTrs
11.88/3.83	    (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
11.88/3.83	    (8) CpxRNTS
11.88/3.83	    (9) CompleteCoflocoProof [FINISHED, 162 ms]
11.88/3.83	    (10) BOUNDS(1, n^2)
11.88/3.83	(11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
11.88/3.83	(12) CpxTRS
11.88/3.83	    (13) SlicingProof [LOWER BOUND(ID), 0 ms]
11.88/3.83	    (14) CpxTRS
11.88/3.83	    (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
11.88/3.83	    (16) typed CpxTrs
11.88/3.83	    (17) OrderProof [LOWER BOUND(ID), 0 ms]
11.88/3.83	    (18) typed CpxTrs
11.88/3.83	    (19) RewriteLemmaProof [LOWER BOUND(ID), 301 ms]
11.88/3.83	    (20) BEST
11.88/3.83	        (21) proven lower bound
11.88/3.83	            (22) LowerBoundPropagationProof [FINISHED, 0 ms]
11.88/3.83	            (23) BOUNDS(n^1, INF)
11.88/3.83	        (24) typed CpxTrs
11.88/3.83	            (25) RewriteLemmaProof [LOWER BOUND(ID), 8 ms]
11.88/3.83	            (26) proven lower bound
11.88/3.83	            (27) LowerBoundPropagationProof [FINISHED, 0 ms]
11.88/3.83	            (28) BOUNDS(n^2, INF)
11.88/3.83	
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(0)
11.88/3.83	Obligation:
11.88/3.83	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2).
11.88/3.83	
11.88/3.83	
11.88/3.83	The TRS R consists of the following rules:
11.88/3.83	
11.88/3.83	   naiverev(Cons(x, xs)) -> app(naiverev(xs), Cons(x, Nil))
11.88/3.83	   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
11.88/3.83	   notEmpty(Cons(x, xs)) -> True
11.88/3.83	   notEmpty(Nil) -> False
11.88/3.83	   naiverev(Nil) -> Nil
11.88/3.83	   app(Nil, ys) -> ys
11.88/3.83	   goal(xs) -> naiverev(xs)
11.88/3.83	
11.88/3.83	S is empty.
11.88/3.83	Rewrite Strategy: INNERMOST
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
11.88/3.83	Transformed relative TRS to weighted TRS
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(2)
11.88/3.83	Obligation:
11.88/3.83	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).
11.88/3.83	
11.88/3.83	
11.88/3.83	The TRS R consists of the following rules:
11.88/3.83	
11.88/3.83	   naiverev(Cons(x, xs)) -> app(naiverev(xs), Cons(x, Nil)) [1]
11.88/3.83	   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1]
11.88/3.83	   notEmpty(Cons(x, xs)) -> True [1]
11.88/3.83	   notEmpty(Nil) -> False [1]
11.88/3.83	   naiverev(Nil) -> Nil [1]
11.88/3.83	   app(Nil, ys) -> ys [1]
11.88/3.83	   goal(xs) -> naiverev(xs) [1]
11.88/3.83	
11.88/3.83	Rewrite Strategy: INNERMOST
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
11.88/3.83	Infered types.
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(4)
11.88/3.83	Obligation:
11.88/3.83	Runtime Complexity Weighted TRS with Types.
11.88/3.83	The TRS R consists of the following rules:
11.88/3.83	
11.88/3.83	   naiverev(Cons(x, xs)) -> app(naiverev(xs), Cons(x, Nil)) [1]
11.88/3.83	   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1]
11.88/3.83	   notEmpty(Cons(x, xs)) -> True [1]
11.88/3.83	   notEmpty(Nil) -> False [1]
11.88/3.83	   naiverev(Nil) -> Nil [1]
11.88/3.83	   app(Nil, ys) -> ys [1]
11.88/3.83	   goal(xs) -> naiverev(xs) [1]
11.88/3.83	
11.88/3.83	The TRS has the following type information:
11.88/3.83	naiverev :: Cons:Nil -> Cons:Nil
11.88/3.83	Cons :: a -> Cons:Nil -> Cons:Nil
11.88/3.83	app :: Cons:Nil -> Cons:Nil -> Cons:Nil
11.88/3.83	Nil :: Cons:Nil
11.88/3.83	notEmpty :: Cons:Nil -> True:False
11.88/3.83	True :: True:False
11.88/3.83	False :: True:False
11.88/3.83	goal :: Cons:Nil -> Cons:Nil
11.88/3.83	
11.88/3.83	Rewrite Strategy: INNERMOST
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(5) CompletionProof (UPPER BOUND(ID))
11.88/3.83	The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
11.88/3.83	none
11.88/3.83	
11.88/3.83	And the following fresh constants:    const
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(6)
11.88/3.83	Obligation:
11.88/3.83	Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:
11.88/3.83	
11.88/3.83	Runtime Complexity Weighted TRS with Types.
11.88/3.83	The TRS R consists of the following rules:
11.88/3.83	
11.88/3.83	   naiverev(Cons(x, xs)) -> app(naiverev(xs), Cons(x, Nil)) [1]
11.88/3.83	   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys)) [1]
11.88/3.83	   notEmpty(Cons(x, xs)) -> True [1]
11.88/3.83	   notEmpty(Nil) -> False [1]
11.88/3.83	   naiverev(Nil) -> Nil [1]
11.88/3.83	   app(Nil, ys) -> ys [1]
11.88/3.83	   goal(xs) -> naiverev(xs) [1]
11.88/3.83	
11.88/3.83	The TRS has the following type information:
11.88/3.83	naiverev :: Cons:Nil -> Cons:Nil
11.88/3.83	Cons :: a -> Cons:Nil -> Cons:Nil
11.88/3.83	app :: Cons:Nil -> Cons:Nil -> Cons:Nil
11.88/3.83	Nil :: Cons:Nil
11.88/3.83	notEmpty :: Cons:Nil -> True:False
11.88/3.83	True :: True:False
11.88/3.83	False :: True:False
11.88/3.83	goal :: Cons:Nil -> Cons:Nil
11.88/3.83	const :: a
11.88/3.83	
11.88/3.83	Rewrite Strategy: INNERMOST
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
11.88/3.83	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
11.88/3.83	The constant constructors are abstracted as follows:
11.88/3.83	
11.88/3.83	   Nil => 0
11.88/3.83	   True => 1
11.88/3.83	   False => 0
11.88/3.83	   const => 0
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(8)
11.88/3.83	Obligation:
11.88/3.83	Complexity RNTS consisting of the following rules:
11.88/3.83	
11.88/3.83	   app(z, z') -{ 1 }-> ys :|: z' = ys, ys >= 0, z = 0
11.88/3.83	   app(z, z') -{ 1 }-> 1 + x + app(xs, ys) :|: z = 1 + x + xs, xs >= 0, z' = ys, ys >= 0, x >= 0
11.88/3.83	   goal(z) -{ 1 }-> naiverev(xs) :|: xs >= 0, z = xs
11.88/3.83	   naiverev(z) -{ 1 }-> app(naiverev(xs), 1 + x + 0) :|: z = 1 + x + xs, xs >= 0, x >= 0
11.88/3.83	   naiverev(z) -{ 1 }-> 0 :|: z = 0
11.88/3.83	   notEmpty(z) -{ 1 }-> 1 :|: z = 1 + x + xs, xs >= 0, x >= 0
11.88/3.83	   notEmpty(z) -{ 1 }-> 0 :|: z = 0
11.88/3.83	
11.88/3.83	Only complete derivations are relevant for the runtime complexity.
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(9) CompleteCoflocoProof (FINISHED)
11.88/3.83	Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:
11.88/3.83	
11.88/3.83	eq(start(V, V3),0,[naiverev(V, Out)],[V >= 0]).
11.88/3.83	eq(start(V, V3),0,[app(V, V3, Out)],[V >= 0,V3 >= 0]).
11.88/3.83	eq(start(V, V3),0,[notEmpty(V, Out)],[V >= 0]).
11.88/3.83	eq(start(V, V3),0,[goal(V, Out)],[V >= 0]).
11.88/3.83	eq(naiverev(V, Out),1,[naiverev(V1, Ret0),app(Ret0, 1 + V2 + 0, Ret)],[Out = Ret,V = 1 + V1 + V2,V1 >= 0,V2 >= 0]).
11.88/3.83	eq(app(V, V3, Out),1,[app(V5, V6, Ret1)],[Out = 1 + Ret1 + V4,V = 1 + V4 + V5,V5 >= 0,V3 = V6,V6 >= 0,V4 >= 0]).
11.88/3.83	eq(notEmpty(V, Out),1,[],[Out = 1,V = 1 + V7 + V8,V8 >= 0,V7 >= 0]).
11.88/3.83	eq(notEmpty(V, Out),1,[],[Out = 0,V = 0]).
11.88/3.83	eq(naiverev(V, Out),1,[],[Out = 0,V = 0]).
11.88/3.83	eq(app(V, V3, Out),1,[],[Out = V9,V3 = V9,V9 >= 0,V = 0]).
11.88/3.83	eq(goal(V, Out),1,[naiverev(V10, Ret2)],[Out = Ret2,V10 >= 0,V = V10]).
11.88/3.83	input_output_vars(naiverev(V,Out),[V],[Out]).
11.88/3.83	input_output_vars(app(V,V3,Out),[V,V3],[Out]).
11.88/3.83	input_output_vars(notEmpty(V,Out),[V],[Out]).
11.88/3.83	input_output_vars(goal(V,Out),[V],[Out]).
11.88/3.83	
11.88/3.83	
11.88/3.83	CoFloCo proof output:
11.88/3.83	Preprocessing Cost Relations
11.88/3.83	=====================================
11.88/3.83	
11.88/3.83	#### Computed strongly connected components 
11.88/3.83	0. recursive  : [app/3]
11.88/3.83	1. recursive [non_tail] : [naiverev/2]
11.88/3.83	2. non_recursive  : [goal/2]
11.88/3.83	3. non_recursive  : [notEmpty/2]
11.88/3.83	4. non_recursive  : [start/2]
11.88/3.83	
11.88/3.83	#### Obtained direct recursion through partial evaluation 
11.88/3.83	0. SCC is partially evaluated into app/3
11.88/3.83	1. SCC is partially evaluated into naiverev/2
11.88/3.83	2. SCC is completely evaluated into other SCCs
11.88/3.83	3. SCC is partially evaluated into notEmpty/2
11.88/3.83	4. SCC is partially evaluated into start/2
11.88/3.83	
11.88/3.83	Control-Flow Refinement of Cost Relations
11.88/3.83	=====================================
11.88/3.83	
11.88/3.83	### Specialization of cost equations app/3 
11.88/3.83	* CE 8 is refined into CE [11] 
11.88/3.83	* CE 7 is refined into CE [12] 
11.88/3.83	
11.88/3.83	
11.88/3.83	### Cost equations --> "Loop" of app/3 
11.88/3.83	* CEs [12] --> Loop 8 
11.88/3.83	* CEs [11] --> Loop 9 
11.88/3.83	
11.88/3.83	### Ranking functions of CR app(V,V3,Out) 
11.88/3.83	* RF of phase [8]: [V]
11.88/3.83	
11.88/3.83	#### Partial ranking functions of CR app(V,V3,Out) 
11.88/3.83	* Partial RF of phase [8]:
11.88/3.83	  - RF of loop [8:1]:
11.88/3.83	    V
11.88/3.83	
11.88/3.83	
11.88/3.83	### Specialization of cost equations naiverev/2 
11.88/3.83	* CE 6 is refined into CE [13] 
11.88/3.83	* CE 5 is refined into CE [14,15] 
11.88/3.83	
11.88/3.83	
11.88/3.83	### Cost equations --> "Loop" of naiverev/2 
11.88/3.83	* CEs [15] --> Loop 10 
11.88/3.83	* CEs [14] --> Loop 11 
11.88/3.83	* CEs [13] --> Loop 12 
11.88/3.83	
11.88/3.83	### Ranking functions of CR naiverev(V,Out) 
11.88/3.83	* RF of phase [10]: [V]
11.88/3.83	
11.88/3.83	#### Partial ranking functions of CR naiverev(V,Out) 
11.88/3.83	* Partial RF of phase [10]:
11.88/3.83	  - RF of loop [10:1]:
11.88/3.83	    V
11.88/3.83	
11.88/3.83	
11.88/3.83	### Specialization of cost equations notEmpty/2 
11.88/3.83	* CE 9 is refined into CE [16] 
11.88/3.83	* CE 10 is refined into CE [17] 
11.88/3.83	
11.88/3.83	
11.88/3.83	### Cost equations --> "Loop" of notEmpty/2 
11.88/3.83	* CEs [16] --> Loop 13 
11.88/3.83	* CEs [17] --> Loop 14 
11.88/3.83	
11.88/3.83	### Ranking functions of CR notEmpty(V,Out) 
11.88/3.83	
11.88/3.83	#### Partial ranking functions of CR notEmpty(V,Out) 
11.88/3.83	
11.88/3.83	
11.88/3.83	### Specialization of cost equations start/2 
11.88/3.83	* CE 1 is refined into CE [18,19] 
11.88/3.83	* CE 2 is refined into CE [20,21] 
11.88/3.83	* CE 3 is refined into CE [22,23] 
11.88/3.83	* CE 4 is refined into CE [24,25] 
11.88/3.83	
11.88/3.83	
11.88/3.83	### Cost equations --> "Loop" of start/2 
11.88/3.83	* CEs [19,21,23,25] --> Loop 15 
11.88/3.83	* CEs [18,20,22,24] --> Loop 16 
11.88/3.83	
11.88/3.83	### Ranking functions of CR start(V,V3) 
11.88/3.83	
11.88/3.83	#### Partial ranking functions of CR start(V,V3) 
11.88/3.83	
11.88/3.83	
11.88/3.83	Computing Bounds
11.88/3.83	=====================================
11.88/3.83	
11.88/3.83	#### Cost of chains of app(V,V3,Out):
11.88/3.83	* Chain [[8],9]: 1*it(8)+1
11.88/3.83	  Such that:it(8) =< -V3+Out
11.88/3.83	
11.88/3.83	  with precondition: [V+V3=Out,V>=1,V3>=0] 
11.88/3.83	
11.88/3.83	* Chain [9]: 1
11.88/3.83	  with precondition: [V=0,V3=Out,V3>=0] 
11.88/3.83	
11.88/3.83	
11.88/3.83	#### Cost of chains of naiverev(V,Out):
11.88/3.83	* Chain [[10],11,12]: 2*it(10)+1*s(3)+3
11.88/3.83	  Such that:aux(3) =< Out
11.88/3.83	it(10) =< aux(3)
11.88/3.83	s(3) =< it(10)*aux(3)
11.88/3.83	
11.88/3.83	  with precondition: [Out=V,Out>=2] 
11.88/3.83	
11.88/3.83	* Chain [12]: 1
11.88/3.83	  with precondition: [V=0,Out=0] 
11.88/3.83	
11.88/3.83	* Chain [11,12]: 3
11.88/3.83	  with precondition: [V=Out,V>=1] 
11.88/3.83	
11.88/3.83	
11.88/3.83	#### Cost of chains of notEmpty(V,Out):
11.88/3.83	* Chain [14]: 1
11.88/3.83	  with precondition: [V=0,Out=0] 
11.88/3.83	
11.88/3.83	* Chain [13]: 1
11.88/3.83	  with precondition: [Out=1,V>=1] 
11.88/3.83	
11.88/3.83	
11.88/3.83	#### Cost of chains of start(V,V3):
11.88/3.83	* Chain [16]: 2
11.88/3.83	  with precondition: [V=0] 
11.88/3.83	
11.88/3.83	* Chain [15]: 5*s(8)+2*s(9)+4
11.88/3.83	  Such that:aux(4) =< V
11.88/3.83	s(8) =< aux(4)
11.88/3.83	s(9) =< s(8)*aux(4)
11.88/3.83	
11.88/3.83	  with precondition: [V>=1] 
11.88/3.83	
11.88/3.83	
11.88/3.83	Closed-form bounds of start(V,V3): 
11.88/3.83	-------------------------------------
11.88/3.83	* Chain [16] with precondition: [V=0] 
11.88/3.83	    - Upper bound: 2 
11.88/3.83	    - Complexity: constant 
11.88/3.83	* Chain [15] with precondition: [V>=1] 
11.88/3.83	    - Upper bound: 5*V+4+2*V*V 
11.88/3.83	    - Complexity: n^2 
11.88/3.83	
11.88/3.83	### Maximum cost of start(V,V3): 5*V+2+2*V*V+2 
11.88/3.83	Asymptotic class: n^2 
11.88/3.83	* Total analysis performed in 99 ms.
11.88/3.83	
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(10)
11.88/3.83	BOUNDS(1, n^2)
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(11) RenamingProof (BOTH BOUNDS(ID, ID))
11.88/3.83	Renamed function symbols to avoid clashes with predefined symbol.
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(12)
11.88/3.83	Obligation:
11.88/3.83	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
11.88/3.83	
11.88/3.83	
11.88/3.83	The TRS R consists of the following rules:
11.88/3.83	
11.88/3.83	   naiverev(Cons(x, xs)) -> app(naiverev(xs), Cons(x, Nil))
11.88/3.83	   app(Cons(x, xs), ys) -> Cons(x, app(xs, ys))
11.88/3.83	   notEmpty(Cons(x, xs)) -> True
11.88/3.83	   notEmpty(Nil) -> False
11.88/3.83	   naiverev(Nil) -> Nil
11.88/3.83	   app(Nil, ys) -> ys
11.88/3.83	   goal(xs) -> naiverev(xs)
11.88/3.83	
11.88/3.83	S is empty.
11.88/3.83	Rewrite Strategy: INNERMOST
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(13) SlicingProof (LOWER BOUND(ID))
11.88/3.83	Sliced the following arguments:
11.88/3.83	Cons/0
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(14)
11.88/3.83	Obligation:
11.88/3.83	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
11.88/3.83	
11.88/3.83	
11.88/3.83	The TRS R consists of the following rules:
11.88/3.83	
11.88/3.83	   naiverev(Cons(xs)) -> app(naiverev(xs), Cons(Nil))
11.88/3.83	   app(Cons(xs), ys) -> Cons(app(xs, ys))
11.88/3.83	   notEmpty(Cons(xs)) -> True
11.88/3.83	   notEmpty(Nil) -> False
11.88/3.83	   naiverev(Nil) -> Nil
11.88/3.83	   app(Nil, ys) -> ys
11.88/3.83	   goal(xs) -> naiverev(xs)
11.88/3.83	
11.88/3.83	S is empty.
11.88/3.83	Rewrite Strategy: INNERMOST
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(15) TypeInferenceProof (BOTH BOUNDS(ID, ID))
11.88/3.83	Infered types.
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(16)
11.88/3.83	Obligation:
11.88/3.83	Innermost TRS:
11.88/3.83	Rules:
11.88/3.83	naiverev(Cons(xs)) -> app(naiverev(xs), Cons(Nil))
11.88/3.83	app(Cons(xs), ys) -> Cons(app(xs, ys))
11.88/3.83	notEmpty(Cons(xs)) -> True
11.88/3.83	notEmpty(Nil) -> False
11.88/3.83	naiverev(Nil) -> Nil
11.88/3.83	app(Nil, ys) -> ys
11.88/3.83	goal(xs) -> naiverev(xs)
11.88/3.83	
11.88/3.83	Types:
11.88/3.83	naiverev :: Cons:Nil -> Cons:Nil
11.88/3.83	Cons :: Cons:Nil -> Cons:Nil
11.88/3.83	app :: Cons:Nil -> Cons:Nil -> Cons:Nil
11.88/3.83	Nil :: Cons:Nil
11.88/3.83	notEmpty :: Cons:Nil -> True:False
11.88/3.83	True :: True:False
11.88/3.83	False :: True:False
11.88/3.83	goal :: Cons:Nil -> Cons:Nil
11.88/3.83	hole_Cons:Nil1_0 :: Cons:Nil
11.88/3.83	hole_True:False2_0 :: True:False
11.88/3.83	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(17) OrderProof (LOWER BOUND(ID))
11.88/3.83	Heuristically decided to analyse the following defined symbols:
11.88/3.83	naiverev, app
11.88/3.83	
11.88/3.83	They will be analysed ascendingly in the following order:
11.88/3.83	app < naiverev
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(18)
11.88/3.83	Obligation:
11.88/3.83	Innermost TRS:
11.88/3.83	Rules:
11.88/3.83	naiverev(Cons(xs)) -> app(naiverev(xs), Cons(Nil))
11.88/3.83	app(Cons(xs), ys) -> Cons(app(xs, ys))
11.88/3.83	notEmpty(Cons(xs)) -> True
11.88/3.83	notEmpty(Nil) -> False
11.88/3.83	naiverev(Nil) -> Nil
11.88/3.83	app(Nil, ys) -> ys
11.88/3.83	goal(xs) -> naiverev(xs)
11.88/3.83	
11.88/3.83	Types:
11.88/3.83	naiverev :: Cons:Nil -> Cons:Nil
11.88/3.83	Cons :: Cons:Nil -> Cons:Nil
11.88/3.83	app :: Cons:Nil -> Cons:Nil -> Cons:Nil
11.88/3.83	Nil :: Cons:Nil
11.88/3.83	notEmpty :: Cons:Nil -> True:False
11.88/3.83	True :: True:False
11.88/3.83	False :: True:False
11.88/3.83	goal :: Cons:Nil -> Cons:Nil
11.88/3.83	hole_Cons:Nil1_0 :: Cons:Nil
11.88/3.83	hole_True:False2_0 :: True:False
11.88/3.83	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
11.88/3.83	
11.88/3.83	
11.88/3.83	Generator Equations:
11.88/3.83	gen_Cons:Nil3_0(0) <=> Nil
11.88/3.83	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x))
11.88/3.83	
11.88/3.83	
11.88/3.83	The following defined symbols remain to be analysed:
11.88/3.83	app, naiverev
11.88/3.83	
11.88/3.83	They will be analysed ascendingly in the following order:
11.88/3.83	app < naiverev
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(19) RewriteLemmaProof (LOWER BOUND(ID))
11.88/3.83	Proved the following rewrite lemma:
11.88/3.83	app(gen_Cons:Nil3_0(n5_0), gen_Cons:Nil3_0(b)) -> gen_Cons:Nil3_0(+(n5_0, b)), rt in Omega(1 + n5_0)
11.88/3.83	
11.88/3.83	Induction Base:
11.88/3.83	app(gen_Cons:Nil3_0(0), gen_Cons:Nil3_0(b)) ->_R^Omega(1)
11.88/3.83	gen_Cons:Nil3_0(b)
11.88/3.83	
11.88/3.83	Induction Step:
11.88/3.83	app(gen_Cons:Nil3_0(+(n5_0, 1)), gen_Cons:Nil3_0(b)) ->_R^Omega(1)
11.88/3.83	Cons(app(gen_Cons:Nil3_0(n5_0), gen_Cons:Nil3_0(b))) ->_IH
11.88/3.83	Cons(gen_Cons:Nil3_0(+(b, c6_0)))
11.88/3.83	
11.88/3.83	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(20)
11.88/3.83	Complex Obligation (BEST)
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(21)
11.88/3.83	Obligation:
11.88/3.83	Proved the lower bound n^1 for the following obligation:
11.88/3.83	
11.88/3.83	Innermost TRS:
11.88/3.83	Rules:
11.88/3.83	naiverev(Cons(xs)) -> app(naiverev(xs), Cons(Nil))
11.88/3.83	app(Cons(xs), ys) -> Cons(app(xs, ys))
11.88/3.83	notEmpty(Cons(xs)) -> True
11.88/3.83	notEmpty(Nil) -> False
11.88/3.83	naiverev(Nil) -> Nil
11.88/3.83	app(Nil, ys) -> ys
11.88/3.83	goal(xs) -> naiverev(xs)
11.88/3.83	
11.88/3.83	Types:
11.88/3.83	naiverev :: Cons:Nil -> Cons:Nil
11.88/3.83	Cons :: Cons:Nil -> Cons:Nil
11.88/3.83	app :: Cons:Nil -> Cons:Nil -> Cons:Nil
11.88/3.83	Nil :: Cons:Nil
11.88/3.83	notEmpty :: Cons:Nil -> True:False
11.88/3.83	True :: True:False
11.88/3.83	False :: True:False
11.88/3.83	goal :: Cons:Nil -> Cons:Nil
11.88/3.83	hole_Cons:Nil1_0 :: Cons:Nil
11.88/3.83	hole_True:False2_0 :: True:False
11.88/3.83	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
11.88/3.83	
11.88/3.83	
11.88/3.83	Generator Equations:
11.88/3.83	gen_Cons:Nil3_0(0) <=> Nil
11.88/3.83	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x))
11.88/3.83	
11.88/3.83	
11.88/3.83	The following defined symbols remain to be analysed:
11.88/3.83	app, naiverev
11.88/3.83	
11.88/3.83	They will be analysed ascendingly in the following order:
11.88/3.83	app < naiverev
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(22) LowerBoundPropagationProof (FINISHED)
11.88/3.83	Propagated lower bound.
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(23)
11.88/3.83	BOUNDS(n^1, INF)
11.88/3.83	
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(24)
11.88/3.83	Obligation:
11.88/3.83	Innermost TRS:
11.88/3.83	Rules:
11.88/3.83	naiverev(Cons(xs)) -> app(naiverev(xs), Cons(Nil))
11.88/3.83	app(Cons(xs), ys) -> Cons(app(xs, ys))
11.88/3.83	notEmpty(Cons(xs)) -> True
11.88/3.83	notEmpty(Nil) -> False
11.88/3.83	naiverev(Nil) -> Nil
11.88/3.83	app(Nil, ys) -> ys
11.88/3.83	goal(xs) -> naiverev(xs)
11.88/3.83	
11.88/3.83	Types:
11.88/3.83	naiverev :: Cons:Nil -> Cons:Nil
11.88/3.83	Cons :: Cons:Nil -> Cons:Nil
11.88/3.83	app :: Cons:Nil -> Cons:Nil -> Cons:Nil
11.88/3.83	Nil :: Cons:Nil
11.88/3.83	notEmpty :: Cons:Nil -> True:False
11.88/3.83	True :: True:False
11.88/3.83	False :: True:False
11.88/3.83	goal :: Cons:Nil -> Cons:Nil
11.88/3.83	hole_Cons:Nil1_0 :: Cons:Nil
11.88/3.83	hole_True:False2_0 :: True:False
11.88/3.83	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
11.88/3.83	
11.88/3.83	
11.88/3.83	Lemmas:
11.88/3.83	app(gen_Cons:Nil3_0(n5_0), gen_Cons:Nil3_0(b)) -> gen_Cons:Nil3_0(+(n5_0, b)), rt in Omega(1 + n5_0)
11.88/3.83	
11.88/3.83	
11.88/3.83	Generator Equations:
11.88/3.83	gen_Cons:Nil3_0(0) <=> Nil
11.88/3.83	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x))
11.88/3.83	
11.88/3.83	
11.88/3.83	The following defined symbols remain to be analysed:
11.88/3.83	naiverev
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(25) RewriteLemmaProof (LOWER BOUND(ID))
11.88/3.83	Proved the following rewrite lemma:
11.88/3.83	naiverev(gen_Cons:Nil3_0(n489_0)) -> gen_Cons:Nil3_0(n489_0), rt in Omega(1 + n489_0 + n489_0^2)
11.88/3.83	
11.88/3.83	Induction Base:
11.88/3.83	naiverev(gen_Cons:Nil3_0(0)) ->_R^Omega(1)
11.88/3.83	Nil
11.88/3.83	
11.88/3.83	Induction Step:
11.88/3.83	naiverev(gen_Cons:Nil3_0(+(n489_0, 1))) ->_R^Omega(1)
11.88/3.83	app(naiverev(gen_Cons:Nil3_0(n489_0)), Cons(Nil)) ->_IH
11.88/3.83	app(gen_Cons:Nil3_0(c490_0), Cons(Nil)) ->_L^Omega(1 + n489_0)
11.88/3.83	gen_Cons:Nil3_0(+(n489_0, +(0, 1)))
11.88/3.83	
11.88/3.83	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(26)
11.88/3.83	Obligation:
11.88/3.83	Proved the lower bound n^2 for the following obligation:
11.88/3.83	
11.88/3.83	Innermost TRS:
11.88/3.83	Rules:
11.88/3.83	naiverev(Cons(xs)) -> app(naiverev(xs), Cons(Nil))
11.88/3.83	app(Cons(xs), ys) -> Cons(app(xs, ys))
11.88/3.83	notEmpty(Cons(xs)) -> True
11.88/3.83	notEmpty(Nil) -> False
11.88/3.83	naiverev(Nil) -> Nil
11.88/3.83	app(Nil, ys) -> ys
11.88/3.83	goal(xs) -> naiverev(xs)
11.88/3.83	
11.88/3.83	Types:
11.88/3.83	naiverev :: Cons:Nil -> Cons:Nil
11.88/3.83	Cons :: Cons:Nil -> Cons:Nil
11.88/3.83	app :: Cons:Nil -> Cons:Nil -> Cons:Nil
11.88/3.83	Nil :: Cons:Nil
11.88/3.83	notEmpty :: Cons:Nil -> True:False
11.88/3.83	True :: True:False
11.88/3.83	False :: True:False
11.88/3.83	goal :: Cons:Nil -> Cons:Nil
11.88/3.83	hole_Cons:Nil1_0 :: Cons:Nil
11.88/3.83	hole_True:False2_0 :: True:False
11.88/3.83	gen_Cons:Nil3_0 :: Nat -> Cons:Nil
11.88/3.83	
11.88/3.83	
11.88/3.83	Lemmas:
11.88/3.83	app(gen_Cons:Nil3_0(n5_0), gen_Cons:Nil3_0(b)) -> gen_Cons:Nil3_0(+(n5_0, b)), rt in Omega(1 + n5_0)
11.88/3.83	
11.88/3.83	
11.88/3.83	Generator Equations:
11.88/3.83	gen_Cons:Nil3_0(0) <=> Nil
11.88/3.83	gen_Cons:Nil3_0(+(x, 1)) <=> Cons(gen_Cons:Nil3_0(x))
11.88/3.83	
11.88/3.83	
11.88/3.83	The following defined symbols remain to be analysed:
11.88/3.83	naiverev
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(27) LowerBoundPropagationProof (FINISHED)
11.88/3.83	Propagated lower bound.
11.88/3.83	----------------------------------------
11.88/3.83	
11.88/3.83	(28)
11.88/3.83	BOUNDS(n^2, INF)
11.90/3.88	EOF