45.53/13.20	WORST_CASE(Omega(n^3), O(n^3))
45.53/13.22	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
45.53/13.22	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
45.53/13.22	
45.53/13.22	
45.53/13.22	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3).
45.53/13.22	
45.53/13.22	(0) CpxTRS
45.53/13.22	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
45.53/13.22	(2) CpxWeightedTrs
45.53/13.22	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
45.53/13.22	    (4) CpxTypedWeightedTrs
45.53/13.22	    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
45.53/13.22	    (6) CpxTypedWeightedCompleteTrs
45.53/13.22	    (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
45.53/13.22	    (8) CpxTypedWeightedCompleteTrs
45.53/13.22	    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
45.53/13.22	    (10) CpxRNTS
45.53/13.22	    (11) SimplificationProof [BOTH BOUNDS(ID, ID), 3 ms]
45.53/13.22	    (12) CpxRNTS
45.53/13.22	    (13) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
45.53/13.22	    (14) CpxRNTS
45.53/13.22	    (15) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
45.53/13.22	    (16) CpxRNTS
45.53/13.22	    (17) IntTrsBoundProof [UPPER BOUND(ID), 201 ms]
45.53/13.22	    (18) CpxRNTS
45.53/13.22	    (19) IntTrsBoundProof [UPPER BOUND(ID), 75 ms]
45.53/13.22	    (20) CpxRNTS
45.53/13.22	    (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
45.53/13.22	    (22) CpxRNTS
45.53/13.22	    (23) IntTrsBoundProof [UPPER BOUND(ID), 341 ms]
45.53/13.22	    (24) CpxRNTS
45.53/13.22	    (25) IntTrsBoundProof [UPPER BOUND(ID), 115 ms]
45.53/13.22	    (26) CpxRNTS
45.53/13.22	    (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
45.53/13.22	    (28) CpxRNTS
45.53/13.22	    (29) IntTrsBoundProof [UPPER BOUND(ID), 505 ms]
45.53/13.22	    (30) CpxRNTS
45.53/13.22	    (31) IntTrsBoundProof [UPPER BOUND(ID), 44 ms]
45.53/13.22	    (32) CpxRNTS
45.53/13.22	    (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
45.53/13.22	    (34) CpxRNTS
45.53/13.22	    (35) IntTrsBoundProof [UPPER BOUND(ID), 738 ms]
45.53/13.22	    (36) CpxRNTS
45.53/13.22	    (37) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
45.53/13.22	    (38) CpxRNTS
45.53/13.22	    (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
45.53/13.22	    (40) CpxRNTS
45.53/13.22	    (41) IntTrsBoundProof [UPPER BOUND(ID), 2708 ms]
45.53/13.22	    (42) CpxRNTS
45.53/13.22	    (43) IntTrsBoundProof [UPPER BOUND(ID), 4 ms]
45.53/13.22	    (44) CpxRNTS
45.53/13.22	    (45) FinalProof [FINISHED, 0 ms]
45.53/13.22	    (46) BOUNDS(1, n^3)
45.53/13.22	(47) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
45.53/13.22	(48) CpxTRS
45.53/13.22	    (49) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
45.53/13.22	    (50) typed CpxTrs
45.53/13.22	    (51) OrderProof [LOWER BOUND(ID), 0 ms]
45.53/13.22	    (52) typed CpxTrs
45.53/13.22	    (53) RewriteLemmaProof [LOWER BOUND(ID), 295 ms]
45.53/13.22	    (54) BEST
45.53/13.22	        (55) proven lower bound
45.53/13.22	            (56) LowerBoundPropagationProof [FINISHED, 0 ms]
45.53/13.22	            (57) BOUNDS(n^1, INF)
45.53/13.22	        (58) typed CpxTrs
45.53/13.22	            (59) RewriteLemmaProof [LOWER BOUND(ID), 106 ms]
45.53/13.22	            (60) typed CpxTrs
45.53/13.22	            (61) RewriteLemmaProof [LOWER BOUND(ID), 105 ms]
45.53/13.22	            (62) BEST
45.53/13.22	                (63) proven lower bound
45.53/13.22	                    (64) LowerBoundPropagationProof [FINISHED, 0 ms]
45.53/13.22	                    (65) BOUNDS(n^3, INF)
45.53/13.22	                (66) typed CpxTrs
45.53/13.22	
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(0)
45.53/13.22	Obligation:
45.53/13.22	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3).
45.53/13.22	
45.53/13.22	
45.53/13.22	The TRS R consists of the following rules:
45.53/13.22	
45.53/13.22	   terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
45.53/13.22	   sqr(0) -> 0
45.53/13.22	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
45.53/13.22	   dbl(0) -> 0
45.53/13.22	   dbl(s(X)) -> s(s(dbl(X)))
45.53/13.22	   add(0, X) -> X
45.53/13.22	   add(s(X), Y) -> s(add(X, Y))
45.53/13.22	   first(0, X) -> nil
45.53/13.22	   first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
45.53/13.22	   terms(X) -> n__terms(X)
45.53/13.22	   first(X1, X2) -> n__first(X1, X2)
45.53/13.22	   activate(n__terms(X)) -> terms(X)
45.53/13.22	   activate(n__first(X1, X2)) -> first(X1, X2)
45.53/13.22	   activate(X) -> X
45.53/13.22	
45.53/13.22	S is empty.
45.53/13.22	Rewrite Strategy: INNERMOST
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
45.53/13.22	Transformed relative TRS to weighted TRS
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(2)
45.53/13.22	Obligation:
45.53/13.22	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3).
45.53/13.22	
45.53/13.22	
45.53/13.22	The TRS R consists of the following rules:
45.53/13.22	
45.53/13.22	   terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) [1]
45.53/13.22	   sqr(0) -> 0 [1]
45.53/13.22	   sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1]
45.53/13.22	   dbl(0) -> 0 [1]
45.53/13.22	   dbl(s(X)) -> s(s(dbl(X))) [1]
45.53/13.22	   add(0, X) -> X [1]
45.53/13.22	   add(s(X), Y) -> s(add(X, Y)) [1]
45.53/13.22	   first(0, X) -> nil [1]
45.53/13.22	   first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) [1]
45.53/13.22	   terms(X) -> n__terms(X) [1]
45.53/13.22	   first(X1, X2) -> n__first(X1, X2) [1]
45.53/13.22	   activate(n__terms(X)) -> terms(X) [1]
45.53/13.22	   activate(n__first(X1, X2)) -> first(X1, X2) [1]
45.53/13.22	   activate(X) -> X [1]
45.53/13.22	
45.53/13.22	Rewrite Strategy: INNERMOST
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
45.53/13.22	Infered types.
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(4)
45.53/13.22	Obligation:
45.53/13.22	Runtime Complexity Weighted TRS with Types.
45.53/13.22	The TRS R consists of the following rules:
45.53/13.22	
45.53/13.22	   terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) [1]
45.53/13.22	   sqr(0) -> 0 [1]
45.53/13.22	   sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1]
45.53/13.22	   dbl(0) -> 0 [1]
45.53/13.22	   dbl(s(X)) -> s(s(dbl(X))) [1]
45.53/13.22	   add(0, X) -> X [1]
45.53/13.22	   add(s(X), Y) -> s(add(X, Y)) [1]
45.53/13.22	   first(0, X) -> nil [1]
45.53/13.22	   first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) [1]
45.53/13.22	   terms(X) -> n__terms(X) [1]
45.53/13.22	   first(X1, X2) -> n__first(X1, X2) [1]
45.53/13.22	   activate(n__terms(X)) -> terms(X) [1]
45.53/13.22	   activate(n__first(X1, X2)) -> first(X1, X2) [1]
45.53/13.22	   activate(X) -> X [1]
45.53/13.22	
45.53/13.22	The TRS has the following type information:
45.53/13.22	terms :: s:0 -> n__terms:cons:nil:n__first
45.53/13.22	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	recip :: s:0 -> recip
45.53/13.22	sqr :: s:0 -> s:0
45.53/13.22	n__terms :: s:0 -> n__terms:cons:nil:n__first
45.53/13.22	s :: s:0 -> s:0
45.53/13.22	0 :: s:0
45.53/13.22	add :: s:0 -> s:0 -> s:0
45.53/13.22	dbl :: s:0 -> s:0
45.53/13.22	first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	nil :: n__terms:cons:nil:n__first
45.53/13.22	n__first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	
45.53/13.22	Rewrite Strategy: INNERMOST
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(5) CompletionProof (UPPER BOUND(ID))
45.53/13.22	The transformation into a RNTS is sound, since:
45.53/13.22	
45.53/13.22	(a) The obligation is a constructor system where every type has a constant constructor,
45.53/13.22	
45.53/13.22	(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
45.53/13.22	
45.53/13.22	   terms_1
45.53/13.22	   first_2
45.53/13.22	   activate_1
45.53/13.22	
45.53/13.22	(c) The following functions are completely defined:
45.53/13.22	
45.53/13.22	   sqr_1
45.53/13.22	   dbl_1
45.53/13.22	   add_2
45.53/13.22	
45.53/13.22	Due to the following rules being added:
45.53/13.22	none
45.53/13.22	
45.53/13.22	And the following fresh constants:    const
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(6)
45.53/13.22	Obligation:
45.53/13.22	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
45.53/13.22	
45.53/13.22	Runtime Complexity Weighted TRS with Types.
45.53/13.22	The TRS R consists of the following rules:
45.53/13.22	
45.53/13.22	   terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) [1]
45.53/13.22	   sqr(0) -> 0 [1]
45.53/13.22	   sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1]
45.53/13.22	   dbl(0) -> 0 [1]
45.53/13.22	   dbl(s(X)) -> s(s(dbl(X))) [1]
45.53/13.22	   add(0, X) -> X [1]
45.53/13.22	   add(s(X), Y) -> s(add(X, Y)) [1]
45.53/13.22	   first(0, X) -> nil [1]
45.53/13.22	   first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) [1]
45.53/13.22	   terms(X) -> n__terms(X) [1]
45.53/13.22	   first(X1, X2) -> n__first(X1, X2) [1]
45.53/13.22	   activate(n__terms(X)) -> terms(X) [1]
45.53/13.22	   activate(n__first(X1, X2)) -> first(X1, X2) [1]
45.53/13.22	   activate(X) -> X [1]
45.53/13.22	
45.53/13.22	The TRS has the following type information:
45.53/13.22	terms :: s:0 -> n__terms:cons:nil:n__first
45.53/13.22	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	recip :: s:0 -> recip
45.53/13.22	sqr :: s:0 -> s:0
45.53/13.22	n__terms :: s:0 -> n__terms:cons:nil:n__first
45.53/13.22	s :: s:0 -> s:0
45.53/13.22	0 :: s:0
45.53/13.22	add :: s:0 -> s:0 -> s:0
45.53/13.22	dbl :: s:0 -> s:0
45.53/13.22	first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	nil :: n__terms:cons:nil:n__first
45.53/13.22	n__first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	const :: recip
45.53/13.22	
45.53/13.22	Rewrite Strategy: INNERMOST
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(7) NarrowingProof (BOTH BOUNDS(ID, ID))
45.53/13.22	Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(8)
45.53/13.22	Obligation:
45.53/13.22	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
45.53/13.22	
45.53/13.22	Runtime Complexity Weighted TRS with Types.
45.53/13.22	The TRS R consists of the following rules:
45.53/13.22	
45.53/13.22	   terms(N) -> cons(recip(sqr(N)), n__terms(s(N))) [1]
45.53/13.22	   sqr(0) -> 0 [1]
45.53/13.22	   sqr(s(0)) -> s(add(0, 0)) [3]
45.53/13.22	   sqr(s(s(X'))) -> s(add(s(add(sqr(X'), dbl(X'))), s(s(dbl(X'))))) [3]
45.53/13.22	   dbl(0) -> 0 [1]
45.53/13.22	   dbl(s(X)) -> s(s(dbl(X))) [1]
45.53/13.22	   add(0, X) -> X [1]
45.53/13.22	   add(s(X), Y) -> s(add(X, Y)) [1]
45.53/13.22	   first(0, X) -> nil [1]
45.53/13.22	   first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z))) [1]
45.53/13.22	   terms(X) -> n__terms(X) [1]
45.53/13.22	   first(X1, X2) -> n__first(X1, X2) [1]
45.53/13.22	   activate(n__terms(X)) -> terms(X) [1]
45.53/13.22	   activate(n__first(X1, X2)) -> first(X1, X2) [1]
45.53/13.22	   activate(X) -> X [1]
45.53/13.22	
45.53/13.22	The TRS has the following type information:
45.53/13.22	terms :: s:0 -> n__terms:cons:nil:n__first
45.53/13.22	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	recip :: s:0 -> recip
45.53/13.22	sqr :: s:0 -> s:0
45.53/13.22	n__terms :: s:0 -> n__terms:cons:nil:n__first
45.53/13.22	s :: s:0 -> s:0
45.53/13.22	0 :: s:0
45.53/13.22	add :: s:0 -> s:0 -> s:0
45.53/13.22	dbl :: s:0 -> s:0
45.53/13.22	first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	nil :: n__terms:cons:nil:n__first
45.53/13.22	n__first :: s:0 -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.22	const :: recip
45.53/13.22	
45.53/13.22	Rewrite Strategy: INNERMOST
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
45.53/13.22	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
45.53/13.22	The constant constructors are abstracted as follows:
45.53/13.22	
45.53/13.22	   0 => 0
45.53/13.22	   nil => 0
45.53/13.22	   const => 0
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(10)
45.53/13.22	Obligation:
45.53/13.22	Complexity RNTS consisting of the following rules:
45.53/13.22	
45.53/13.22	   activate(z) -{ 1 }-> X :|: X >= 0, z = X
45.53/13.22	   activate(z) -{ 1 }-> terms(X) :|: z = 1 + X, X >= 0
45.53/13.22	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.22	   add(z, z') -{ 1 }-> X :|: z' = X, X >= 0, z = 0
45.53/13.22	   add(z, z') -{ 1 }-> 1 + add(X, Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0
45.53/13.22	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   dbl(z) -{ 1 }-> 1 + (1 + dbl(X)) :|: z = 1 + X, X >= 0
45.53/13.22	   first(z, z') -{ 1 }-> 0 :|: z' = X, X >= 0, z = 0
45.53/13.22	   first(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2
45.53/13.22	   first(z, z') -{ 1 }-> 1 + Y + (1 + X + activate(Z)) :|: Z >= 0, z = 1 + X, Y >= 0, X >= 0, z' = 1 + Y + Z
45.53/13.22	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(X'), dbl(X')), 1 + (1 + dbl(X'))) :|: X' >= 0, z = 1 + (1 + X')
45.53/13.22	   terms(z) -{ 1 }-> 1 + X :|: X >= 0, z = X
45.53/13.22	   terms(z) -{ 1 }-> 1 + (1 + sqr(N)) + (1 + (1 + N)) :|: z = N, N >= 0
45.53/13.22	
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(11) SimplificationProof (BOTH BOUNDS(ID, ID))
45.53/13.22	Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(12)
45.53/13.22	Obligation:
45.53/13.22	Complexity RNTS consisting of the following rules:
45.53/13.22	
45.53/13.22	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.22	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.22	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.22	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.22	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
45.53/13.22	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
45.53/13.22	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.22	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.22	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.22	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
45.53/13.22	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.22	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.22	
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(13) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
45.53/13.22	Found the following analysis order by SCC decomposition:
45.53/13.22	
45.53/13.22	   { dbl }
45.53/13.22	   { add }
45.53/13.22	   { sqr }
45.53/13.22	   { terms }
45.53/13.22	   { first, activate }
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(14)
45.53/13.22	Obligation:
45.53/13.22	Complexity RNTS consisting of the following rules:
45.53/13.22	
45.53/13.22	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.22	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.22	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.22	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.22	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
45.53/13.22	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
45.53/13.22	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.22	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.22	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.22	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
45.53/13.22	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.22	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.22	
45.53/13.22	Function symbols to be analyzed: {dbl}, {add}, {sqr}, {terms}, {first,activate}
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(15) ResultPropagationProof (UPPER BOUND(ID))
45.53/13.22	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(16)
45.53/13.22	Obligation:
45.53/13.22	Complexity RNTS consisting of the following rules:
45.53/13.22	
45.53/13.22	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.22	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.22	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.22	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.22	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
45.53/13.22	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
45.53/13.22	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.22	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.22	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.22	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
45.53/13.22	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.22	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.22	
45.53/13.22	Function symbols to be analyzed: {dbl}, {add}, {sqr}, {terms}, {first,activate}
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(17) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.22	
45.53/13.22	Computed SIZE bound using CoFloCo for: dbl
45.53/13.22	after applying outer abstraction to obtain an ITS,
45.53/13.22	resulting in: O(n^1) with polynomial bound: 2*z
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(18)
45.53/13.22	Obligation:
45.53/13.22	Complexity RNTS consisting of the following rules:
45.53/13.22	
45.53/13.22	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.22	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.22	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.22	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.22	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
45.53/13.22	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
45.53/13.22	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.22	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.22	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.22	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
45.53/13.22	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
45.53/13.22	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.22	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.22	
45.53/13.22	Function symbols to be analyzed: {dbl}, {add}, {sqr}, {terms}, {first,activate}
45.53/13.22	Previous analysis results are:
45.53/13.22	  dbl: runtime: ?, size: O(n^1) [2*z]
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(19) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.22	
45.53/13.22	Computed RUNTIME bound using CoFloCo for: dbl
45.53/13.22	after applying outer abstraction to obtain an ITS,
45.53/13.22	resulting in: O(n^1) with polynomial bound: 1 + z
45.53/13.22	
45.53/13.22	----------------------------------------
45.53/13.22	
45.53/13.22	(20)
45.53/13.22	Obligation:
45.53/13.22	Complexity RNTS consisting of the following rules:
45.53/13.22	
45.53/13.22	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.22	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.22	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.22	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.22	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
45.53/13.22	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.22	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
45.53/13.22	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.22	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.22	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.22	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
45.53/13.24	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {add}, {sqr}, {terms}, {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(21) ResultPropagationProof (UPPER BOUND(ID))
45.53/13.24	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(22)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
45.53/13.24	   sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {add}, {sqr}, {terms}, {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(23) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.24	
45.53/13.24	Computed SIZE bound using CoFloCo for: add
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: O(n^1) with polynomial bound: z + z'
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(24)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
45.53/13.24	   sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {add}, {sqr}, {terms}, {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: ?, size: O(n^1) [z + z']
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(25) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.24	
45.53/13.24	Computed RUNTIME bound using CoFloCo for: add
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: O(n^1) with polynomial bound: 1 + z
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(26)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
45.53/13.24	   sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {sqr}, {terms}, {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(27) ResultPropagationProof (UPPER BOUND(ID))
45.53/13.24	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(28)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
45.53/13.24	   sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {sqr}, {terms}, {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(29) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.24	
45.53/13.24	Computed SIZE bound using KoAT for: sqr
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: O(n^2) with polynomial bound: 1 + 4*z + 4*z^2
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(30)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
45.53/13.24	   sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {sqr}, {terms}, {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	  sqr: runtime: ?, size: O(n^2) [1 + 4*z + 4*z^2]
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(31) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.24	
45.53/13.24	Computed RUNTIME bound using KoAT for: sqr
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: O(n^3) with polynomial bound: 5 + 22*z + 8*z^3
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(32)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
45.53/13.24	   sqr(z) -{ 1 + 2*z }-> 1 + add(1 + add(sqr(z - 2), s), 1 + (1 + s')) :|: s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) + (1 + (1 + z)) :|: z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {terms}, {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(33) ResultPropagationProof (UPPER BOUND(ID))
45.53/13.24	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(34)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
45.53/13.24	   sqr(z) -{ -99 + s4 + s5 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s6 :|: s4 >= 0, s4 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s5 >= 0, s5 <= s4 + s, s6 >= 0, s6 <= 1 + s5 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s3) + (1 + (1 + z)) :|: s3 >= 0, s3 <= 4 * (z * z) + 4 * z + 1, z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {terms}, {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(35) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.24	
45.53/13.24	Computed SIZE bound using KoAT for: terms
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: O(n^2) with polynomial bound: 6 + 6*z + 4*z^2
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(36)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
45.53/13.24	   sqr(z) -{ -99 + s4 + s5 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s6 :|: s4 >= 0, s4 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s5 >= 0, s5 <= s4 + s, s6 >= 0, s6 <= 1 + s5 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s3) + (1 + (1 + z)) :|: s3 >= 0, s3 <= 4 * (z * z) + 4 * z + 1, z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {terms}, {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
45.53/13.24	  terms: runtime: ?, size: O(n^2) [6 + 6*z + 4*z^2]
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(37) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.24	
45.53/13.24	Computed RUNTIME bound using KoAT for: terms
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: O(n^3) with polynomial bound: 7 + 22*z + 8*z^3
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(38)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> terms(z - 1) :|: z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
45.53/13.24	   sqr(z) -{ -99 + s4 + s5 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s6 :|: s4 >= 0, s4 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s5 >= 0, s5 <= s4 + s, s6 >= 0, s6 <= 1 + s5 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s3) + (1 + (1 + z)) :|: s3 >= 0, s3 <= 4 * (z * z) + 4 * z + 1, z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
45.53/13.24	  terms: runtime: O(n^3) [7 + 22*z + 8*z^3], size: O(n^2) [6 + 6*z + 4*z^2]
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(39) ResultPropagationProof (UPPER BOUND(ID))
45.53/13.24	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(40)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ -22 + 46*z + -24*z^2 + 8*z^3 }-> s7 :|: s7 >= 0, s7 <= 6 * (z - 1) + 4 * ((z - 1) * (z - 1)) + 6, z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
45.53/13.24	   sqr(z) -{ -99 + s4 + s5 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s6 :|: s4 >= 0, s4 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s5 >= 0, s5 <= s4 + s, s6 >= 0, s6 <= 1 + s5 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s3) + (1 + (1 + z)) :|: s3 >= 0, s3 <= 4 * (z * z) + 4 * z + 1, z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
45.53/13.24	  terms: runtime: O(n^3) [7 + 22*z + 8*z^3], size: O(n^2) [6 + 6*z + 4*z^2]
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(41) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.24	
45.53/13.24	Computed SIZE bound using CoFloCo for: first
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: INF with polynomial bound: ?
45.53/13.24	
45.53/13.24	Computed SIZE bound using CoFloCo for: activate
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: INF with polynomial bound: ?
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(42)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ -22 + 46*z + -24*z^2 + 8*z^3 }-> s7 :|: s7 >= 0, s7 <= 6 * (z - 1) + 4 * ((z - 1) * (z - 1)) + 6, z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
45.53/13.24	   sqr(z) -{ -99 + s4 + s5 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s6 :|: s4 >= 0, s4 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s5 >= 0, s5 <= s4 + s, s6 >= 0, s6 <= 1 + s5 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s3) + (1 + (1 + z)) :|: s3 >= 0, s3 <= 4 * (z * z) + 4 * z + 1, z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: {first,activate}
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
45.53/13.24	  terms: runtime: O(n^3) [7 + 22*z + 8*z^3], size: O(n^2) [6 + 6*z + 4*z^2]
45.53/13.24	  first: runtime: ?, size: INF
45.53/13.24	  activate: runtime: ?, size: INF
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(43) IntTrsBoundProof (UPPER BOUND(ID))
45.53/13.24	
45.53/13.24	Computed RUNTIME bound using KoAT for: first
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: O(n^3) with polynomial bound: 3 + 48*z' + 8*z'^3
45.53/13.24	
45.53/13.24	Computed RUNTIME bound using KoAT for: activate
45.53/13.24	after applying outer abstraction to obtain an ITS,
45.53/13.24	resulting in: O(n^3) with polynomial bound: 5 + 94*z + 16*z^3
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(44)
45.53/13.24	Obligation:
45.53/13.24	Complexity RNTS consisting of the following rules:
45.53/13.24	
45.53/13.24	   activate(z) -{ -22 + 46*z + -24*z^2 + 8*z^3 }-> s7 :|: s7 >= 0, s7 <= 6 * (z - 1) + 4 * ((z - 1) * (z - 1)) + 6, z - 1 >= 0
45.53/13.24	   activate(z) -{ 1 }-> z :|: z >= 0
45.53/13.24	   activate(z) -{ 1 }-> first(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
45.53/13.24	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
45.53/13.24	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
45.53/13.24	   dbl(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
45.53/13.24	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
45.53/13.24	   first(z, z') -{ 1 }-> 1 + Y + (1 + (z - 1) + activate(Z)) :|: Z >= 0, Y >= 0, z - 1 >= 0, z' = 1 + Y + Z
45.53/13.24	   first(z, z') -{ 1 }-> 1 + z + z' :|: z >= 0, z' >= 0
45.53/13.24	   sqr(z) -{ 1 }-> 0 :|: z = 0
45.53/13.24	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
45.53/13.24	   sqr(z) -{ -99 + s4 + s5 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s6 :|: s4 >= 0, s4 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s5 >= 0, s5 <= s4 + s, s6 >= 0, s6 <= 1 + s5 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
45.53/13.24	   terms(z) -{ 1 }-> 1 + z :|: z >= 0
45.53/13.24	   terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s3) + (1 + (1 + z)) :|: s3 >= 0, s3 <= 4 * (z * z) + 4 * z + 1, z >= 0
45.53/13.24	
45.53/13.24	Function symbols to be analyzed: 
45.53/13.24	Previous analysis results are:
45.53/13.24	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
45.53/13.24	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
45.53/13.24	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
45.53/13.24	  terms: runtime: O(n^3) [7 + 22*z + 8*z^3], size: O(n^2) [6 + 6*z + 4*z^2]
45.53/13.24	  first: runtime: O(n^3) [3 + 48*z' + 8*z'^3], size: INF
45.53/13.24	  activate: runtime: O(n^3) [5 + 94*z + 16*z^3], size: INF
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(45) FinalProof (FINISHED)
45.53/13.24	Computed overall runtime complexity
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(46)
45.53/13.24	BOUNDS(1, n^3)
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(47) RenamingProof (BOTH BOUNDS(ID, ID))
45.53/13.24	Renamed function symbols to avoid clashes with predefined symbol.
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(48)
45.53/13.24	Obligation:
45.53/13.24	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).
45.53/13.24	
45.53/13.24	
45.53/13.24	The TRS R consists of the following rules:
45.53/13.24	
45.53/13.24	   terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
45.53/13.24	   sqr(0') -> 0'
45.53/13.24	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
45.53/13.24	   dbl(0') -> 0'
45.53/13.24	   dbl(s(X)) -> s(s(dbl(X)))
45.53/13.24	   add(0', X) -> X
45.53/13.24	   add(s(X), Y) -> s(add(X, Y))
45.53/13.24	   first(0', X) -> nil
45.53/13.24	   first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
45.53/13.24	   terms(X) -> n__terms(X)
45.53/13.24	   first(X1, X2) -> n__first(X1, X2)
45.53/13.24	   activate(n__terms(X)) -> terms(X)
45.53/13.24	   activate(n__first(X1, X2)) -> first(X1, X2)
45.53/13.24	   activate(X) -> X
45.53/13.24	
45.53/13.24	S is empty.
45.53/13.24	Rewrite Strategy: INNERMOST
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(49) TypeInferenceProof (BOTH BOUNDS(ID, ID))
45.53/13.24	Infered types.
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(50)
45.53/13.24	Obligation:
45.53/13.24	Innermost TRS:
45.53/13.24	Rules:
45.53/13.24	terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
45.53/13.24	sqr(0') -> 0'
45.53/13.24	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
45.53/13.24	dbl(0') -> 0'
45.53/13.24	dbl(s(X)) -> s(s(dbl(X)))
45.53/13.24	add(0', X) -> X
45.53/13.24	add(s(X), Y) -> s(add(X, Y))
45.53/13.24	first(0', X) -> nil
45.53/13.24	first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
45.53/13.24	terms(X) -> n__terms(X)
45.53/13.24	first(X1, X2) -> n__first(X1, X2)
45.53/13.24	activate(n__terms(X)) -> terms(X)
45.53/13.24	activate(n__first(X1, X2)) -> first(X1, X2)
45.53/13.24	activate(X) -> X
45.53/13.24	
45.53/13.24	Types:
45.53/13.24	terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	recip :: s:0' -> recip
45.53/13.24	sqr :: s:0' -> s:0'
45.53/13.24	n__terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	s :: s:0' -> s:0'
45.53/13.24	0' :: s:0'
45.53/13.24	add :: s:0' -> s:0' -> s:0'
45.53/13.24	dbl :: s:0' -> s:0'
45.53/13.24	first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	nil :: n__terms:cons:nil:n__first
45.53/13.24	n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first
45.53/13.24	hole_s:0'2_0 :: s:0'
45.53/13.24	hole_recip3_0 :: recip
45.53/13.24	gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first
45.53/13.24	gen_s:0'5_0 :: Nat -> s:0'
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(51) OrderProof (LOWER BOUND(ID))
45.53/13.24	Heuristically decided to analyse the following defined symbols:
45.53/13.24	sqr, add, dbl, activate
45.53/13.24	
45.53/13.24	They will be analysed ascendingly in the following order:
45.53/13.24	add < sqr
45.53/13.24	dbl < sqr
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(52)
45.53/13.24	Obligation:
45.53/13.24	Innermost TRS:
45.53/13.24	Rules:
45.53/13.24	terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
45.53/13.24	sqr(0') -> 0'
45.53/13.24	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
45.53/13.24	dbl(0') -> 0'
45.53/13.24	dbl(s(X)) -> s(s(dbl(X)))
45.53/13.24	add(0', X) -> X
45.53/13.24	add(s(X), Y) -> s(add(X, Y))
45.53/13.24	first(0', X) -> nil
45.53/13.24	first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
45.53/13.24	terms(X) -> n__terms(X)
45.53/13.24	first(X1, X2) -> n__first(X1, X2)
45.53/13.24	activate(n__terms(X)) -> terms(X)
45.53/13.24	activate(n__first(X1, X2)) -> first(X1, X2)
45.53/13.24	activate(X) -> X
45.53/13.24	
45.53/13.24	Types:
45.53/13.24	terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	recip :: s:0' -> recip
45.53/13.24	sqr :: s:0' -> s:0'
45.53/13.24	n__terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	s :: s:0' -> s:0'
45.53/13.24	0' :: s:0'
45.53/13.24	add :: s:0' -> s:0' -> s:0'
45.53/13.24	dbl :: s:0' -> s:0'
45.53/13.24	first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	nil :: n__terms:cons:nil:n__first
45.53/13.24	n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first
45.53/13.24	hole_s:0'2_0 :: s:0'
45.53/13.24	hole_recip3_0 :: recip
45.53/13.24	gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first
45.53/13.24	gen_s:0'5_0 :: Nat -> s:0'
45.53/13.24	
45.53/13.24	
45.53/13.24	Generator Equations:
45.53/13.24	gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0')
45.53/13.24	gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x))
45.53/13.24	gen_s:0'5_0(0) <=> 0'
45.53/13.24	gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x))
45.53/13.24	
45.53/13.24	
45.53/13.24	The following defined symbols remain to be analysed:
45.53/13.24	add, sqr, dbl, activate
45.53/13.24	
45.53/13.24	They will be analysed ascendingly in the following order:
45.53/13.24	add < sqr
45.53/13.24	dbl < sqr
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(53) RewriteLemmaProof (LOWER BOUND(ID))
45.53/13.24	Proved the following rewrite lemma:
45.53/13.24	add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0)
45.53/13.24	
45.53/13.24	Induction Base:
45.53/13.24	add(gen_s:0'5_0(0), gen_s:0'5_0(b)) ->_R^Omega(1)
45.53/13.24	gen_s:0'5_0(b)
45.53/13.24	
45.53/13.24	Induction Step:
45.53/13.24	add(gen_s:0'5_0(+(n7_0, 1)), gen_s:0'5_0(b)) ->_R^Omega(1)
45.53/13.24	s(add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b))) ->_IH
45.53/13.24	s(gen_s:0'5_0(+(b, c8_0)))
45.53/13.24	
45.53/13.24	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(54)
45.53/13.24	Complex Obligation (BEST)
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(55)
45.53/13.24	Obligation:
45.53/13.24	Proved the lower bound n^1 for the following obligation:
45.53/13.24	
45.53/13.24	Innermost TRS:
45.53/13.24	Rules:
45.53/13.24	terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
45.53/13.24	sqr(0') -> 0'
45.53/13.24	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
45.53/13.24	dbl(0') -> 0'
45.53/13.24	dbl(s(X)) -> s(s(dbl(X)))
45.53/13.24	add(0', X) -> X
45.53/13.24	add(s(X), Y) -> s(add(X, Y))
45.53/13.24	first(0', X) -> nil
45.53/13.24	first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
45.53/13.24	terms(X) -> n__terms(X)
45.53/13.24	first(X1, X2) -> n__first(X1, X2)
45.53/13.24	activate(n__terms(X)) -> terms(X)
45.53/13.24	activate(n__first(X1, X2)) -> first(X1, X2)
45.53/13.24	activate(X) -> X
45.53/13.24	
45.53/13.24	Types:
45.53/13.24	terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	recip :: s:0' -> recip
45.53/13.24	sqr :: s:0' -> s:0'
45.53/13.24	n__terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	s :: s:0' -> s:0'
45.53/13.24	0' :: s:0'
45.53/13.24	add :: s:0' -> s:0' -> s:0'
45.53/13.24	dbl :: s:0' -> s:0'
45.53/13.24	first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	nil :: n__terms:cons:nil:n__first
45.53/13.24	n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first
45.53/13.24	hole_s:0'2_0 :: s:0'
45.53/13.24	hole_recip3_0 :: recip
45.53/13.24	gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first
45.53/13.24	gen_s:0'5_0 :: Nat -> s:0'
45.53/13.24	
45.53/13.24	
45.53/13.24	Generator Equations:
45.53/13.24	gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0')
45.53/13.24	gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x))
45.53/13.24	gen_s:0'5_0(0) <=> 0'
45.53/13.24	gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x))
45.53/13.24	
45.53/13.24	
45.53/13.24	The following defined symbols remain to be analysed:
45.53/13.24	add, sqr, dbl, activate
45.53/13.24	
45.53/13.24	They will be analysed ascendingly in the following order:
45.53/13.24	add < sqr
45.53/13.24	dbl < sqr
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(56) LowerBoundPropagationProof (FINISHED)
45.53/13.24	Propagated lower bound.
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(57)
45.53/13.24	BOUNDS(n^1, INF)
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(58)
45.53/13.24	Obligation:
45.53/13.24	Innermost TRS:
45.53/13.24	Rules:
45.53/13.24	terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
45.53/13.24	sqr(0') -> 0'
45.53/13.24	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
45.53/13.24	dbl(0') -> 0'
45.53/13.24	dbl(s(X)) -> s(s(dbl(X)))
45.53/13.24	add(0', X) -> X
45.53/13.24	add(s(X), Y) -> s(add(X, Y))
45.53/13.24	first(0', X) -> nil
45.53/13.24	first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
45.53/13.24	terms(X) -> n__terms(X)
45.53/13.24	first(X1, X2) -> n__first(X1, X2)
45.53/13.24	activate(n__terms(X)) -> terms(X)
45.53/13.24	activate(n__first(X1, X2)) -> first(X1, X2)
45.53/13.24	activate(X) -> X
45.53/13.24	
45.53/13.24	Types:
45.53/13.24	terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	recip :: s:0' -> recip
45.53/13.24	sqr :: s:0' -> s:0'
45.53/13.24	n__terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	s :: s:0' -> s:0'
45.53/13.24	0' :: s:0'
45.53/13.24	add :: s:0' -> s:0' -> s:0'
45.53/13.24	dbl :: s:0' -> s:0'
45.53/13.24	first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	nil :: n__terms:cons:nil:n__first
45.53/13.24	n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first
45.53/13.24	hole_s:0'2_0 :: s:0'
45.53/13.24	hole_recip3_0 :: recip
45.53/13.24	gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first
45.53/13.24	gen_s:0'5_0 :: Nat -> s:0'
45.53/13.24	
45.53/13.24	
45.53/13.24	Lemmas:
45.53/13.24	add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0)
45.53/13.24	
45.53/13.24	
45.53/13.24	Generator Equations:
45.53/13.24	gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0')
45.53/13.24	gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x))
45.53/13.24	gen_s:0'5_0(0) <=> 0'
45.53/13.24	gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x))
45.53/13.24	
45.53/13.24	
45.53/13.24	The following defined symbols remain to be analysed:
45.53/13.24	dbl, sqr, activate
45.53/13.24	
45.53/13.24	They will be analysed ascendingly in the following order:
45.53/13.24	dbl < sqr
45.53/13.24	
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(59) RewriteLemmaProof (LOWER BOUND(ID))
45.53/13.24	Proved the following rewrite lemma:
45.53/13.24	dbl(gen_s:0'5_0(n836_0)) -> gen_s:0'5_0(*(2, n836_0)), rt in Omega(1 + n836_0)
45.53/13.24	
45.53/13.24	Induction Base:
45.53/13.24	dbl(gen_s:0'5_0(0)) ->_R^Omega(1)
45.53/13.24	0'
45.53/13.24	
45.53/13.24	Induction Step:
45.53/13.24	dbl(gen_s:0'5_0(+(n836_0, 1))) ->_R^Omega(1)
45.53/13.24	s(s(dbl(gen_s:0'5_0(n836_0)))) ->_IH
45.53/13.24	s(s(gen_s:0'5_0(*(2, c837_0))))
45.53/13.24	
45.53/13.24	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(60)
45.53/13.24	Obligation:
45.53/13.24	Innermost TRS:
45.53/13.24	Rules:
45.53/13.24	terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
45.53/13.24	sqr(0') -> 0'
45.53/13.24	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
45.53/13.24	dbl(0') -> 0'
45.53/13.24	dbl(s(X)) -> s(s(dbl(X)))
45.53/13.24	add(0', X) -> X
45.53/13.24	add(s(X), Y) -> s(add(X, Y))
45.53/13.24	first(0', X) -> nil
45.53/13.24	first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
45.53/13.24	terms(X) -> n__terms(X)
45.53/13.24	first(X1, X2) -> n__first(X1, X2)
45.53/13.24	activate(n__terms(X)) -> terms(X)
45.53/13.24	activate(n__first(X1, X2)) -> first(X1, X2)
45.53/13.24	activate(X) -> X
45.53/13.24	
45.53/13.24	Types:
45.53/13.24	terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	recip :: s:0' -> recip
45.53/13.24	sqr :: s:0' -> s:0'
45.53/13.24	n__terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.24	s :: s:0' -> s:0'
45.53/13.24	0' :: s:0'
45.53/13.24	add :: s:0' -> s:0' -> s:0'
45.53/13.24	dbl :: s:0' -> s:0'
45.53/13.24	first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	nil :: n__terms:cons:nil:n__first
45.53/13.24	n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.24	hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first
45.53/13.24	hole_s:0'2_0 :: s:0'
45.53/13.24	hole_recip3_0 :: recip
45.53/13.24	gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first
45.53/13.24	gen_s:0'5_0 :: Nat -> s:0'
45.53/13.24	
45.53/13.24	
45.53/13.24	Lemmas:
45.53/13.24	add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0)
45.53/13.24	dbl(gen_s:0'5_0(n836_0)) -> gen_s:0'5_0(*(2, n836_0)), rt in Omega(1 + n836_0)
45.53/13.24	
45.53/13.24	
45.53/13.24	Generator Equations:
45.53/13.24	gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0')
45.53/13.24	gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x))
45.53/13.24	gen_s:0'5_0(0) <=> 0'
45.53/13.24	gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x))
45.53/13.24	
45.53/13.24	
45.53/13.24	The following defined symbols remain to be analysed:
45.53/13.24	sqr, activate
45.53/13.24	----------------------------------------
45.53/13.24	
45.53/13.24	(61) RewriteLemmaProof (LOWER BOUND(ID))
45.53/13.24	Proved the following rewrite lemma:
45.53/13.24	sqr(gen_s:0'5_0(n1166_0)) -> gen_s:0'5_0(*(n1166_0, n1166_0)), rt in Omega(1 + n1166_0 + n1166_0^2 + n1166_0^3)
45.53/13.24	
45.53/13.24	Induction Base:
45.53/13.24	sqr(gen_s:0'5_0(0)) ->_R^Omega(1)
45.53/13.24	0'
45.53/13.24	
45.53/13.24	Induction Step:
45.53/13.24	sqr(gen_s:0'5_0(+(n1166_0, 1))) ->_R^Omega(1)
45.53/13.24	s(add(sqr(gen_s:0'5_0(n1166_0)), dbl(gen_s:0'5_0(n1166_0)))) ->_IH
45.53/13.24	s(add(gen_s:0'5_0(*(c1167_0, c1167_0)), dbl(gen_s:0'5_0(n1166_0)))) ->_L^Omega(1 + n1166_0)
45.53/13.25	s(add(gen_s:0'5_0(*(n1166_0, n1166_0)), gen_s:0'5_0(*(2, n1166_0)))) ->_L^Omega(1 + n1166_0^2)
45.53/13.25	s(gen_s:0'5_0(+(*(n1166_0, n1166_0), *(2, n1166_0))))
45.53/13.25	
45.53/13.25	We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3).
45.53/13.25	----------------------------------------
45.53/13.25	
45.53/13.25	(62)
45.53/13.25	Complex Obligation (BEST)
45.53/13.25	
45.53/13.25	----------------------------------------
45.53/13.25	
45.53/13.25	(63)
45.53/13.25	Obligation:
45.53/13.25	Proved the lower bound n^3 for the following obligation:
45.53/13.25	
45.53/13.25	Innermost TRS:
45.53/13.25	Rules:
45.53/13.25	terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
45.53/13.25	sqr(0') -> 0'
45.53/13.25	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
45.53/13.25	dbl(0') -> 0'
45.53/13.25	dbl(s(X)) -> s(s(dbl(X)))
45.53/13.25	add(0', X) -> X
45.53/13.25	add(s(X), Y) -> s(add(X, Y))
45.53/13.25	first(0', X) -> nil
45.53/13.25	first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
45.53/13.25	terms(X) -> n__terms(X)
45.53/13.25	first(X1, X2) -> n__first(X1, X2)
45.53/13.25	activate(n__terms(X)) -> terms(X)
45.53/13.25	activate(n__first(X1, X2)) -> first(X1, X2)
45.53/13.25	activate(X) -> X
45.53/13.25	
45.53/13.25	Types:
45.53/13.25	terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.25	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.25	recip :: s:0' -> recip
45.53/13.25	sqr :: s:0' -> s:0'
45.53/13.25	n__terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.25	s :: s:0' -> s:0'
45.53/13.25	0' :: s:0'
45.53/13.25	add :: s:0' -> s:0' -> s:0'
45.53/13.25	dbl :: s:0' -> s:0'
45.53/13.25	first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.25	nil :: n__terms:cons:nil:n__first
45.53/13.25	n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.25	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.25	hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first
45.53/13.25	hole_s:0'2_0 :: s:0'
45.53/13.25	hole_recip3_0 :: recip
45.53/13.25	gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first
45.53/13.25	gen_s:0'5_0 :: Nat -> s:0'
45.53/13.25	
45.53/13.25	
45.53/13.25	Lemmas:
45.53/13.25	add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0)
45.53/13.25	dbl(gen_s:0'5_0(n836_0)) -> gen_s:0'5_0(*(2, n836_0)), rt in Omega(1 + n836_0)
45.53/13.25	
45.53/13.25	
45.53/13.25	Generator Equations:
45.53/13.25	gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0')
45.53/13.25	gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x))
45.53/13.25	gen_s:0'5_0(0) <=> 0'
45.53/13.25	gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x))
45.53/13.25	
45.53/13.25	
45.53/13.25	The following defined symbols remain to be analysed:
45.53/13.25	sqr, activate
45.53/13.25	----------------------------------------
45.53/13.25	
45.53/13.25	(64) LowerBoundPropagationProof (FINISHED)
45.53/13.25	Propagated lower bound.
45.53/13.25	----------------------------------------
45.53/13.25	
45.53/13.25	(65)
45.53/13.25	BOUNDS(n^3, INF)
45.53/13.25	
45.53/13.25	----------------------------------------
45.53/13.25	
45.53/13.25	(66)
45.53/13.25	Obligation:
45.53/13.25	Innermost TRS:
45.53/13.25	Rules:
45.53/13.25	terms(N) -> cons(recip(sqr(N)), n__terms(s(N)))
45.53/13.25	sqr(0') -> 0'
45.53/13.25	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
45.53/13.25	dbl(0') -> 0'
45.53/13.25	dbl(s(X)) -> s(s(dbl(X)))
45.53/13.25	add(0', X) -> X
45.53/13.25	add(s(X), Y) -> s(add(X, Y))
45.53/13.25	first(0', X) -> nil
45.53/13.25	first(s(X), cons(Y, Z)) -> cons(Y, n__first(X, activate(Z)))
45.53/13.25	terms(X) -> n__terms(X)
45.53/13.25	first(X1, X2) -> n__first(X1, X2)
45.53/13.25	activate(n__terms(X)) -> terms(X)
45.53/13.25	activate(n__first(X1, X2)) -> first(X1, X2)
45.53/13.25	activate(X) -> X
45.53/13.25	
45.53/13.25	Types:
45.53/13.25	terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.25	cons :: recip -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.25	recip :: s:0' -> recip
45.53/13.25	sqr :: s:0' -> s:0'
45.53/13.25	n__terms :: s:0' -> n__terms:cons:nil:n__first
45.53/13.25	s :: s:0' -> s:0'
45.53/13.25	0' :: s:0'
45.53/13.25	add :: s:0' -> s:0' -> s:0'
45.53/13.25	dbl :: s:0' -> s:0'
45.53/13.25	first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.25	nil :: n__terms:cons:nil:n__first
45.53/13.25	n__first :: s:0' -> n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.25	activate :: n__terms:cons:nil:n__first -> n__terms:cons:nil:n__first
45.53/13.25	hole_n__terms:cons:nil:n__first1_0 :: n__terms:cons:nil:n__first
45.53/13.25	hole_s:0'2_0 :: s:0'
45.53/13.25	hole_recip3_0 :: recip
45.53/13.25	gen_n__terms:cons:nil:n__first4_0 :: Nat -> n__terms:cons:nil:n__first
45.53/13.25	gen_s:0'5_0 :: Nat -> s:0'
45.53/13.25	
45.53/13.25	
45.53/13.25	Lemmas:
45.53/13.25	add(gen_s:0'5_0(n7_0), gen_s:0'5_0(b)) -> gen_s:0'5_0(+(n7_0, b)), rt in Omega(1 + n7_0)
45.53/13.25	dbl(gen_s:0'5_0(n836_0)) -> gen_s:0'5_0(*(2, n836_0)), rt in Omega(1 + n836_0)
45.53/13.25	sqr(gen_s:0'5_0(n1166_0)) -> gen_s:0'5_0(*(n1166_0, n1166_0)), rt in Omega(1 + n1166_0 + n1166_0^2 + n1166_0^3)
45.53/13.25	
45.53/13.25	
45.53/13.25	Generator Equations:
45.53/13.25	gen_n__terms:cons:nil:n__first4_0(0) <=> n__terms(0')
45.53/13.25	gen_n__terms:cons:nil:n__first4_0(+(x, 1)) <=> cons(recip(0'), gen_n__terms:cons:nil:n__first4_0(x))
45.53/13.25	gen_s:0'5_0(0) <=> 0'
45.53/13.25	gen_s:0'5_0(+(x, 1)) <=> s(gen_s:0'5_0(x))
45.53/13.25	
45.53/13.25	
45.53/13.25	The following defined symbols remain to be analysed:
45.53/13.25	activate
45.76/13.30	EOF