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