1093.07/291.59	WORST_CASE(Omega(n^3), O(n^3))
1093.07/291.61	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
1093.07/291.61	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3).
1093.07/291.61	
1093.07/291.61	(0) CpxTRS
1093.07/291.61	(1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	(2) CpxTRS
1093.07/291.61	    (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms]
1093.07/291.61	    (4) CpxTRS
1093.07/291.61	    (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
1093.07/291.61	    (6) CpxWeightedTrs
1093.07/291.61	    (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1093.07/291.61	    (8) CpxTypedWeightedTrs
1093.07/291.61	    (9) CompletionProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	    (10) CpxTypedWeightedCompleteTrs
1093.07/291.61	    (11) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
1093.07/291.61	    (12) CpxTypedWeightedCompleteTrs
1093.07/291.61	    (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	    (14) CpxRNTS
1093.07/291.61	    (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
1093.07/291.61	    (16) CpxRNTS
1093.07/291.61	    (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
1093.07/291.61	    (18) CpxRNTS
1093.07/291.61	    (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	    (20) CpxRNTS
1093.07/291.61	    (21) IntTrsBoundProof [UPPER BOUND(ID), 215 ms]
1093.07/291.61	    (22) CpxRNTS
1093.07/291.61	    (23) IntTrsBoundProof [UPPER BOUND(ID), 77 ms]
1093.07/291.61	    (24) CpxRNTS
1093.07/291.61	    (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	    (26) CpxRNTS
1093.07/291.61	    (27) IntTrsBoundProof [UPPER BOUND(ID), 252 ms]
1093.07/291.61	    (28) CpxRNTS
1093.07/291.61	    (29) IntTrsBoundProof [UPPER BOUND(ID), 55 ms]
1093.07/291.61	    (30) CpxRNTS
1093.07/291.61	    (31) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	    (32) CpxRNTS
1093.07/291.61	    (33) IntTrsBoundProof [UPPER BOUND(ID), 291 ms]
1093.07/291.61	    (34) CpxRNTS
1093.07/291.61	    (35) IntTrsBoundProof [UPPER BOUND(ID), 135 ms]
1093.07/291.61	    (36) CpxRNTS
1093.07/291.61	    (37) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	    (38) CpxRNTS
1093.07/291.61	    (39) IntTrsBoundProof [UPPER BOUND(ID), 271 ms]
1093.07/291.61	    (40) CpxRNTS
1093.07/291.61	    (41) IntTrsBoundProof [UPPER BOUND(ID), 83 ms]
1093.07/291.61	    (42) CpxRNTS
1093.07/291.61	    (43) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	    (44) CpxRNTS
1093.07/291.61	    (45) IntTrsBoundProof [UPPER BOUND(ID), 534 ms]
1093.07/291.61	    (46) CpxRNTS
1093.07/291.61	    (47) IntTrsBoundProof [UPPER BOUND(ID), 84 ms]
1093.07/291.61	    (48) CpxRNTS
1093.07/291.61	    (49) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	    (50) CpxRNTS
1093.07/291.61	    (51) IntTrsBoundProof [UPPER BOUND(ID), 588 ms]
1093.07/291.61	    (52) CpxRNTS
1093.07/291.61	    (53) IntTrsBoundProof [UPPER BOUND(ID), 0 ms]
1093.07/291.61	    (54) CpxRNTS
1093.07/291.61	    (55) FinalProof [FINISHED, 0 ms]
1093.07/291.61	    (56) BOUNDS(1, n^3)
1093.07/291.61	(57) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
1093.07/291.61	(58) CpxTRS
1093.07/291.61	    (59) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1093.07/291.61	    (60) typed CpxTrs
1093.07/291.61	    (61) OrderProof [LOWER BOUND(ID), 0 ms]
1093.07/291.61	    (62) typed CpxTrs
1093.07/291.61	    (63) RewriteLemmaProof [LOWER BOUND(ID), 288 ms]
1093.07/291.61	    (64) BEST
1093.07/291.61	        (65) proven lower bound
1093.07/291.61	            (66) LowerBoundPropagationProof [FINISHED, 0 ms]
1093.07/291.61	            (67) BOUNDS(n^1, INF)
1093.07/291.61	        (68) typed CpxTrs
1093.07/291.61	            (69) RewriteLemmaProof [LOWER BOUND(ID), 89 ms]
1093.07/291.61	            (70) typed CpxTrs
1093.07/291.61	            (71) RewriteLemmaProof [LOWER BOUND(ID), 93 ms]
1093.07/291.61	            (72) BEST
1093.07/291.61	                (73) proven lower bound
1093.07/291.61	                    (74) LowerBoundPropagationProof [FINISHED, 0 ms]
1093.07/291.61	                    (75) BOUNDS(n^3, INF)
1093.07/291.61	                (76) typed CpxTrs
1093.07/291.61	                    (77) RewriteLemmaProof [LOWER BOUND(ID), 26 ms]
1093.07/291.61	                    (78) BOUNDS(1, INF)
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(0)
1093.07/291.61	Obligation:
1093.07/291.61	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3).
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	The TRS R consists of the following rules:
1093.07/291.61	
1093.07/291.61	   terms(N) -> cons(recip(sqr(N)))
1093.07/291.61	   sqr(0) -> 0
1093.07/291.61	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.61	   dbl(0) -> 0
1093.07/291.61	   dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.61	   add(0, X) -> X
1093.07/291.61	   add(s(X), Y) -> s(add(X, Y))
1093.07/291.61	   first(0, X) -> nil
1093.07/291.61	   first(s(X), cons(Y)) -> cons(Y)
1093.07/291.61	   half(0) -> 0
1093.07/291.61	   half(s(0)) -> 0
1093.07/291.61	   half(s(s(X))) -> s(half(X))
1093.07/291.61	   half(dbl(X)) -> X
1093.07/291.61	
1093.07/291.61	S is empty.
1093.07/291.61	Rewrite Strategy: FULL
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(1) NestedDefinedSymbolProof (UPPER BOUND(ID))
1093.07/291.61	The following defined symbols can occur below the 0th argument of add: sqr, add, dbl
1093.07/291.61	The following defined symbols can occur below the 1th argument of add: dbl
1093.07/291.61	
1093.07/291.61	Hence, the left-hand sides of the following rules are not basic-reachable and can be removed:
1093.07/291.61	half(dbl(X)) -> X
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(2)
1093.07/291.61	Obligation:
1093.07/291.61	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^3).
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	The TRS R consists of the following rules:
1093.07/291.61	
1093.07/291.61	   terms(N) -> cons(recip(sqr(N)))
1093.07/291.61	   sqr(0) -> 0
1093.07/291.61	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.61	   dbl(0) -> 0
1093.07/291.61	   dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.61	   add(0, X) -> X
1093.07/291.61	   add(s(X), Y) -> s(add(X, Y))
1093.07/291.61	   first(0, X) -> nil
1093.07/291.61	   first(s(X), cons(Y)) -> cons(Y)
1093.07/291.61	   half(0) -> 0
1093.07/291.61	   half(s(0)) -> 0
1093.07/291.61	   half(s(s(X))) -> s(half(X))
1093.07/291.61	
1093.07/291.61	S is empty.
1093.07/291.61	Rewrite Strategy: FULL
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(3) RcToIrcProof (BOTH BOUNDS(ID, ID))
1093.07/291.61	Converted rc-obligation to irc-obligation.
1093.07/291.61	
1093.07/291.61	The duplicating contexts are:
1093.07/291.61	sqr(s([]))
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	The defined contexts are:
1093.07/291.61	add([], x1)
1093.07/291.61	add(x0, [])
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc.
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(4)
1093.07/291.61	Obligation:
1093.07/291.61	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^3).
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	The TRS R consists of the following rules:
1093.07/291.61	
1093.07/291.61	   terms(N) -> cons(recip(sqr(N)))
1093.07/291.61	   sqr(0) -> 0
1093.07/291.61	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.61	   dbl(0) -> 0
1093.07/291.61	   dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.61	   add(0, X) -> X
1093.07/291.61	   add(s(X), Y) -> s(add(X, Y))
1093.07/291.61	   first(0, X) -> nil
1093.07/291.61	   first(s(X), cons(Y)) -> cons(Y)
1093.07/291.61	   half(0) -> 0
1093.07/291.61	   half(s(0)) -> 0
1093.07/291.61	   half(s(s(X))) -> s(half(X))
1093.07/291.61	
1093.07/291.61	S is empty.
1093.07/291.61	Rewrite Strategy: INNERMOST
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
1093.07/291.61	Transformed relative TRS to weighted TRS
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(6)
1093.07/291.61	Obligation:
1093.07/291.61	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3).
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	The TRS R consists of the following rules:
1093.07/291.61	
1093.07/291.61	   terms(N) -> cons(recip(sqr(N))) [1]
1093.07/291.61	   sqr(0) -> 0 [1]
1093.07/291.61	   sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1]
1093.07/291.61	   dbl(0) -> 0 [1]
1093.07/291.61	   dbl(s(X)) -> s(s(dbl(X))) [1]
1093.07/291.61	   add(0, X) -> X [1]
1093.07/291.61	   add(s(X), Y) -> s(add(X, Y)) [1]
1093.07/291.61	   first(0, X) -> nil [1]
1093.07/291.61	   first(s(X), cons(Y)) -> cons(Y) [1]
1093.07/291.61	   half(0) -> 0 [1]
1093.07/291.61	   half(s(0)) -> 0 [1]
1093.07/291.61	   half(s(s(X))) -> s(half(X)) [1]
1093.07/291.61	
1093.07/291.61	Rewrite Strategy: INNERMOST
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(7) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1093.07/291.61	Infered types.
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(8)
1093.07/291.61	Obligation:
1093.07/291.61	Runtime Complexity Weighted TRS with Types.
1093.07/291.61	The TRS R consists of the following rules:
1093.07/291.61	
1093.07/291.61	   terms(N) -> cons(recip(sqr(N))) [1]
1093.07/291.61	   sqr(0) -> 0 [1]
1093.07/291.61	   sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1]
1093.07/291.61	   dbl(0) -> 0 [1]
1093.07/291.61	   dbl(s(X)) -> s(s(dbl(X))) [1]
1093.07/291.61	   add(0, X) -> X [1]
1093.07/291.61	   add(s(X), Y) -> s(add(X, Y)) [1]
1093.07/291.61	   first(0, X) -> nil [1]
1093.07/291.61	   first(s(X), cons(Y)) -> cons(Y) [1]
1093.07/291.61	   half(0) -> 0 [1]
1093.07/291.61	   half(s(0)) -> 0 [1]
1093.07/291.61	   half(s(s(X))) -> s(half(X)) [1]
1093.07/291.61	
1093.07/291.61	The TRS has the following type information:
1093.07/291.61	terms :: 0:s -> cons:nil
1093.07/291.61	cons :: recip -> cons:nil
1093.07/291.61	recip :: 0:s -> recip
1093.07/291.61	sqr :: 0:s -> 0:s
1093.07/291.61	0 :: 0:s
1093.07/291.61	s :: 0:s -> 0:s
1093.07/291.61	add :: 0:s -> 0:s -> 0:s
1093.07/291.61	dbl :: 0:s -> 0:s
1093.07/291.61	first :: 0:s -> cons:nil -> cons:nil
1093.07/291.61	nil :: cons:nil
1093.07/291.61	half :: 0:s -> 0:s
1093.07/291.61	
1093.07/291.61	Rewrite Strategy: INNERMOST
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(9) CompletionProof (UPPER BOUND(ID))
1093.07/291.61	The transformation into a RNTS is sound, since:
1093.07/291.61	
1093.07/291.61	(a) The obligation is a constructor system where every type has a constant constructor,
1093.07/291.61	
1093.07/291.61	(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
1093.07/291.61	
1093.07/291.61	   terms_1
1093.07/291.61	   first_2
1093.07/291.61	   half_1
1093.07/291.61	
1093.07/291.61	(c) The following functions are completely defined:
1093.07/291.61	
1093.07/291.61	   sqr_1
1093.07/291.61	   dbl_1
1093.07/291.61	   add_2
1093.07/291.61	
1093.07/291.61	Due to the following rules being added:
1093.07/291.61	none
1093.07/291.61	
1093.07/291.61	And the following fresh constants:    const
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(10)
1093.07/291.61	Obligation:
1093.07/291.61	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
1093.07/291.61	
1093.07/291.61	Runtime Complexity Weighted TRS with Types.
1093.07/291.61	The TRS R consists of the following rules:
1093.07/291.61	
1093.07/291.61	   terms(N) -> cons(recip(sqr(N))) [1]
1093.07/291.61	   sqr(0) -> 0 [1]
1093.07/291.61	   sqr(s(X)) -> s(add(sqr(X), dbl(X))) [1]
1093.07/291.61	   dbl(0) -> 0 [1]
1093.07/291.61	   dbl(s(X)) -> s(s(dbl(X))) [1]
1093.07/291.61	   add(0, X) -> X [1]
1093.07/291.61	   add(s(X), Y) -> s(add(X, Y)) [1]
1093.07/291.61	   first(0, X) -> nil [1]
1093.07/291.61	   first(s(X), cons(Y)) -> cons(Y) [1]
1093.07/291.61	   half(0) -> 0 [1]
1093.07/291.61	   half(s(0)) -> 0 [1]
1093.07/291.61	   half(s(s(X))) -> s(half(X)) [1]
1093.07/291.61	
1093.07/291.61	The TRS has the following type information:
1093.07/291.61	terms :: 0:s -> cons:nil
1093.07/291.61	cons :: recip -> cons:nil
1093.07/291.61	recip :: 0:s -> recip
1093.07/291.61	sqr :: 0:s -> 0:s
1093.07/291.61	0 :: 0:s
1093.07/291.61	s :: 0:s -> 0:s
1093.07/291.61	add :: 0:s -> 0:s -> 0:s
1093.07/291.61	dbl :: 0:s -> 0:s
1093.07/291.61	first :: 0:s -> cons:nil -> cons:nil
1093.07/291.61	nil :: cons:nil
1093.07/291.61	half :: 0:s -> 0:s
1093.07/291.61	const :: recip
1093.07/291.61	
1093.07/291.61	Rewrite Strategy: INNERMOST
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(11) NarrowingProof (BOTH BOUNDS(ID, ID))
1093.07/291.61	Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(12)
1093.07/291.61	Obligation:
1093.07/291.61	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
1093.07/291.61	
1093.07/291.61	Runtime Complexity Weighted TRS with Types.
1093.07/291.61	The TRS R consists of the following rules:
1093.07/291.61	
1093.07/291.61	   terms(N) -> cons(recip(sqr(N))) [1]
1093.07/291.61	   sqr(0) -> 0 [1]
1093.07/291.61	   sqr(s(0)) -> s(add(0, 0)) [3]
1093.07/291.61	   sqr(s(s(X'))) -> s(add(s(add(sqr(X'), dbl(X'))), s(s(dbl(X'))))) [3]
1093.07/291.61	   dbl(0) -> 0 [1]
1093.07/291.61	   dbl(s(X)) -> s(s(dbl(X))) [1]
1093.07/291.61	   add(0, X) -> X [1]
1093.07/291.61	   add(s(X), Y) -> s(add(X, Y)) [1]
1093.07/291.61	   first(0, X) -> nil [1]
1093.07/291.61	   first(s(X), cons(Y)) -> cons(Y) [1]
1093.07/291.61	   half(0) -> 0 [1]
1093.07/291.61	   half(s(0)) -> 0 [1]
1093.07/291.61	   half(s(s(X))) -> s(half(X)) [1]
1093.07/291.61	
1093.07/291.61	The TRS has the following type information:
1093.07/291.61	terms :: 0:s -> cons:nil
1093.07/291.61	cons :: recip -> cons:nil
1093.07/291.61	recip :: 0:s -> recip
1093.07/291.61	sqr :: 0:s -> 0:s
1093.07/291.61	0 :: 0:s
1093.07/291.61	s :: 0:s -> 0:s
1093.07/291.61	add :: 0:s -> 0:s -> 0:s
1093.07/291.61	dbl :: 0:s -> 0:s
1093.07/291.61	first :: 0:s -> cons:nil -> cons:nil
1093.07/291.61	nil :: cons:nil
1093.07/291.61	half :: 0:s -> 0:s
1093.07/291.61	const :: recip
1093.07/291.61	
1093.07/291.61	Rewrite Strategy: INNERMOST
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
1093.07/291.61	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
1093.07/291.61	The constant constructors are abstracted as follows:
1093.07/291.61	
1093.07/291.61	   0 => 0
1093.07/291.61	   nil => 0
1093.07/291.61	   const => 0
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(14)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> X :|: z' = X, X >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(X, Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 }-> 1 + (1 + dbl(X)) :|: z = 1 + X, X >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' = X, X >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + Y :|: z = 1 + X, Y >= 0, z' = 1 + Y, X >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(X) :|: z = 1 + (1 + X), X >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(X'), dbl(X')), 1 + (1 + dbl(X'))) :|: X' >= 0, z = 1 + (1 + X')
1093.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(N)) :|: z = N, N >= 0
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(15) SimplificationProof (BOTH BOUNDS(ID, ID))
1093.07/291.61	Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(16)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
1093.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
1093.07/291.61	Found the following analysis order by SCC decomposition:
1093.07/291.61	
1093.07/291.61	   { first }
1093.07/291.61	   { dbl }
1093.07/291.61	   { add }
1093.07/291.61	   { half }
1093.07/291.61	   { sqr }
1093.07/291.61	   { terms }
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(18)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
1093.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {first}, {dbl}, {add}, {half}, {sqr}, {terms}
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(19) ResultPropagationProof (UPPER BOUND(ID))
1093.07/291.61	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(20)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
1093.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {first}, {dbl}, {add}, {half}, {sqr}, {terms}
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(21) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.61	
1093.07/291.61	Computed SIZE bound using CoFloCo for: first
1093.07/291.61	after applying outer abstraction to obtain an ITS,
1093.07/291.61	resulting in: O(n^1) with polynomial bound: z'
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(22)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
1093.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {first}, {dbl}, {add}, {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: ?, size: O(n^1) [z']
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(23) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.61	
1093.07/291.61	Computed RUNTIME bound using CoFloCo for: first
1093.07/291.61	after applying outer abstraction to obtain an ITS,
1093.07/291.61	resulting in: O(1) with polynomial bound: 1
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(24)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
1093.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {dbl}, {add}, {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(25) ResultPropagationProof (UPPER BOUND(ID))
1093.07/291.61	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(26)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
1093.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {dbl}, {add}, {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(27) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.61	
1093.07/291.61	Computed SIZE bound using CoFloCo for: dbl
1093.07/291.61	after applying outer abstraction to obtain an ITS,
1093.07/291.61	resulting in: O(n^1) with polynomial bound: 2*z
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(28)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
1093.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {dbl}, {add}, {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	  dbl: runtime: ?, size: O(n^1) [2*z]
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(29) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.61	
1093.07/291.61	Computed RUNTIME bound using CoFloCo for: dbl
1093.07/291.61	after applying outer abstraction to obtain an ITS,
1093.07/291.61	resulting in: O(n^1) with polynomial bound: 1 + z
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(30)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 }-> 1 + (1 + dbl(z - 1)) :|: z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(1 + add(sqr(z - 2), dbl(z - 2)), 1 + (1 + dbl(z - 2))) :|: z - 2 >= 0
1093.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {add}, {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(31) ResultPropagationProof (UPPER BOUND(ID))
1093.07/291.61	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(32)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   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.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {add}, {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(33) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.61	
1093.07/291.61	Computed SIZE bound using CoFloCo for: add
1093.07/291.61	after applying outer abstraction to obtain an ITS,
1093.07/291.61	resulting in: O(n^1) with polynomial bound: z + z'
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(34)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   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.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {add}, {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.61	  add: runtime: ?, size: O(n^1) [z + z']
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(35) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.61	
1093.07/291.61	Computed RUNTIME bound using CoFloCo for: add
1093.07/291.61	after applying outer abstraction to obtain an ITS,
1093.07/291.61	resulting in: O(n^1) with polynomial bound: 1 + z
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(36)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 }-> 1 + add(z - 1, z') :|: z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 3 }-> 1 + add(0, 0) :|: z = 1 + 0
1093.07/291.61	   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.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.61	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(37) ResultPropagationProof (UPPER BOUND(ID))
1093.07/291.61	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(38)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
1093.07/291.61	   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.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.61	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(39) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.61	
1093.07/291.61	Computed SIZE bound using KoAT for: half
1093.07/291.61	after applying outer abstraction to obtain an ITS,
1093.07/291.61	resulting in: O(n^1) with polynomial bound: z
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(40)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
1093.07/291.61	   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.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {half}, {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.61	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.61	  half: runtime: ?, size: O(n^1) [z]
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(41) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.61	
1093.07/291.61	Computed RUNTIME bound using CoFloCo for: half
1093.07/291.61	after applying outer abstraction to obtain an ITS,
1093.07/291.61	resulting in: O(n^1) with polynomial bound: 2 + z
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(42)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 }-> 1 + half(z - 2) :|: z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
1093.07/291.61	   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.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.61	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.61	  half: runtime: O(n^1) [2 + z], size: O(n^1) [z]
1093.07/291.61	
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(43) ResultPropagationProof (UPPER BOUND(ID))
1093.07/291.61	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1093.07/291.61	----------------------------------------
1093.07/291.61	
1093.07/291.61	(44)
1093.07/291.61	Obligation:
1093.07/291.61	Complexity RNTS consisting of the following rules:
1093.07/291.61	
1093.07/291.61	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.61	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
1093.07/291.61	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.61	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.61	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.61	   half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0
1093.07/291.61	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.61	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
1093.07/291.61	   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.07/291.61	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.61	
1093.07/291.61	Function symbols to be analyzed: {sqr}, {terms}
1093.07/291.61	Previous analysis results are:
1093.07/291.61	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.61	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.62	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.62	  half: runtime: O(n^1) [2 + z], size: O(n^1) [z]
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(45) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.62	
1093.07/291.62	Computed SIZE bound using KoAT for: sqr
1093.07/291.62	after applying outer abstraction to obtain an ITS,
1093.07/291.62	resulting in: O(n^2) with polynomial bound: 1 + 4*z + 4*z^2
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(46)
1093.07/291.62	Obligation:
1093.07/291.62	Complexity RNTS consisting of the following rules:
1093.07/291.62	
1093.07/291.62	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.62	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
1093.07/291.62	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.62	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.62	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.62	   half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0
1093.07/291.62	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
1093.07/291.62	   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.07/291.62	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.62	
1093.07/291.62	Function symbols to be analyzed: {sqr}, {terms}
1093.07/291.62	Previous analysis results are:
1093.07/291.62	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.62	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.62	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.62	  half: runtime: O(n^1) [2 + z], size: O(n^1) [z]
1093.07/291.62	  sqr: runtime: ?, size: O(n^2) [1 + 4*z + 4*z^2]
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(47) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.62	
1093.07/291.62	Computed RUNTIME bound using KoAT for: sqr
1093.07/291.62	after applying outer abstraction to obtain an ITS,
1093.07/291.62	resulting in: O(n^3) with polynomial bound: 5 + 22*z + 8*z^3
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(48)
1093.07/291.62	Obligation:
1093.07/291.62	Complexity RNTS consisting of the following rules:
1093.07/291.62	
1093.07/291.62	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.62	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
1093.07/291.62	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.62	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.62	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.62	   half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0
1093.07/291.62	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
1093.07/291.62	   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.07/291.62	   terms(z) -{ 1 }-> 1 + (1 + sqr(z)) :|: z >= 0
1093.07/291.62	
1093.07/291.62	Function symbols to be analyzed: {terms}
1093.07/291.62	Previous analysis results are:
1093.07/291.62	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.62	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.62	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.62	  half: runtime: O(n^1) [2 + z], size: O(n^1) [z]
1093.07/291.62	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(49) ResultPropagationProof (UPPER BOUND(ID))
1093.07/291.62	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(50)
1093.07/291.62	Obligation:
1093.07/291.62	Complexity RNTS consisting of the following rules:
1093.07/291.62	
1093.07/291.62	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.62	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
1093.07/291.62	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.62	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.62	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.62	   half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0
1093.07/291.62	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
1093.07/291.62	   sqr(z) -{ -99 + s5 + s6 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s7 :|: s5 >= 0, s5 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s6 >= 0, s6 <= s5 + s, s7 >= 0, s7 <= 1 + s6 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
1093.07/291.62	   terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s4) :|: s4 >= 0, s4 <= 4 * (z * z) + 4 * z + 1, z >= 0
1093.07/291.62	
1093.07/291.62	Function symbols to be analyzed: {terms}
1093.07/291.62	Previous analysis results are:
1093.07/291.62	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.62	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.62	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.62	  half: runtime: O(n^1) [2 + z], size: O(n^1) [z]
1093.07/291.62	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(51) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.62	
1093.07/291.62	Computed SIZE bound using KoAT for: terms
1093.07/291.62	after applying outer abstraction to obtain an ITS,
1093.07/291.62	resulting in: O(n^2) with polynomial bound: 3 + 4*z + 4*z^2
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(52)
1093.07/291.62	Obligation:
1093.07/291.62	Complexity RNTS consisting of the following rules:
1093.07/291.62	
1093.07/291.62	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.62	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
1093.07/291.62	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.62	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.62	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.62	   half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0
1093.07/291.62	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
1093.07/291.62	   sqr(z) -{ -99 + s5 + s6 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s7 :|: s5 >= 0, s5 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s6 >= 0, s6 <= s5 + s, s7 >= 0, s7 <= 1 + s6 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
1093.07/291.62	   terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s4) :|: s4 >= 0, s4 <= 4 * (z * z) + 4 * z + 1, z >= 0
1093.07/291.62	
1093.07/291.62	Function symbols to be analyzed: {terms}
1093.07/291.62	Previous analysis results are:
1093.07/291.62	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.62	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.62	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.62	  half: runtime: O(n^1) [2 + z], size: O(n^1) [z]
1093.07/291.62	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
1093.07/291.62	  terms: runtime: ?, size: O(n^2) [3 + 4*z + 4*z^2]
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(53) IntTrsBoundProof (UPPER BOUND(ID))
1093.07/291.62	
1093.07/291.62	Computed RUNTIME bound using KoAT for: terms
1093.07/291.62	after applying outer abstraction to obtain an ITS,
1093.07/291.62	resulting in: O(n^3) with polynomial bound: 6 + 22*z + 8*z^3
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(54)
1093.07/291.62	Obligation:
1093.07/291.62	Complexity RNTS consisting of the following rules:
1093.07/291.62	
1093.07/291.62	   add(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
1093.07/291.62	   add(z, z') -{ 1 + z }-> 1 + s2 :|: s2 >= 0, s2 <= z - 1 + z', z' >= 0, z - 1 >= 0
1093.07/291.62	   dbl(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   dbl(z) -{ 1 + z }-> 1 + (1 + s'') :|: s'' >= 0, s'' <= 2 * (z - 1), z - 1 >= 0
1093.07/291.62	   first(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
1093.07/291.62	   first(z, z') -{ 1 }-> 1 + (z' - 1) :|: z' - 1 >= 0, z - 1 >= 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   half(z) -{ 1 }-> 0 :|: z = 1 + 0
1093.07/291.62	   half(z) -{ 1 + z }-> 1 + s3 :|: s3 >= 0, s3 <= z - 2, z - 2 >= 0
1093.07/291.62	   sqr(z) -{ 1 }-> 0 :|: z = 0
1093.07/291.62	   sqr(z) -{ 4 }-> 1 + s1 :|: s1 >= 0, s1 <= 0 + 0, z = 1 + 0
1093.07/291.62	   sqr(z) -{ -99 + s5 + s6 + 120*z + -48*z^2 + 8*z^3 }-> 1 + s7 :|: s5 >= 0, s5 <= 4 * ((z - 2) * (z - 2)) + 4 * (z - 2) + 1, s6 >= 0, s6 <= s5 + s, s7 >= 0, s7 <= 1 + s6 + (1 + (1 + s')), s >= 0, s <= 2 * (z - 2), s' >= 0, s' <= 2 * (z - 2), z - 2 >= 0
1093.07/291.62	   terms(z) -{ 6 + 22*z + 8*z^3 }-> 1 + (1 + s4) :|: s4 >= 0, s4 <= 4 * (z * z) + 4 * z + 1, z >= 0
1093.07/291.62	
1093.07/291.62	Function symbols to be analyzed: 
1093.07/291.62	Previous analysis results are:
1093.07/291.62	  first: runtime: O(1) [1], size: O(n^1) [z']
1093.07/291.62	  dbl: runtime: O(n^1) [1 + z], size: O(n^1) [2*z]
1093.07/291.62	  add: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
1093.07/291.62	  half: runtime: O(n^1) [2 + z], size: O(n^1) [z]
1093.07/291.62	  sqr: runtime: O(n^3) [5 + 22*z + 8*z^3], size: O(n^2) [1 + 4*z + 4*z^2]
1093.07/291.62	  terms: runtime: O(n^3) [6 + 22*z + 8*z^3], size: O(n^2) [3 + 4*z + 4*z^2]
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(55) FinalProof (FINISHED)
1093.07/291.62	Computed overall runtime complexity
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(56)
1093.07/291.62	BOUNDS(1, n^3)
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(57) RenamingProof (BOTH BOUNDS(ID, ID))
1093.07/291.62	Renamed function symbols to avoid clashes with predefined symbol.
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(58)
1093.07/291.62	Obligation:
1093.07/291.62	The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	The TRS R consists of the following rules:
1093.07/291.62	
1093.07/291.62	   terms(N) -> cons(recip(sqr(N)))
1093.07/291.62	   sqr(0') -> 0'
1093.07/291.62	   sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.62	   dbl(0') -> 0'
1093.07/291.62	   dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.62	   add(0', X) -> X
1093.07/291.62	   add(s(X), Y) -> s(add(X, Y))
1093.07/291.62	   first(0', X) -> nil
1093.07/291.62	   first(s(X), cons(Y)) -> cons(Y)
1093.07/291.62	   half(0') -> 0'
1093.07/291.62	   half(s(0')) -> 0'
1093.07/291.62	   half(s(s(X))) -> s(half(X))
1093.07/291.62	   half(dbl(X)) -> X
1093.07/291.62	
1093.07/291.62	S is empty.
1093.07/291.62	Rewrite Strategy: FULL
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(59) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1093.07/291.62	Infered types.
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(60)
1093.07/291.62	Obligation:
1093.07/291.62	TRS:
1093.07/291.62	Rules:
1093.07/291.62	terms(N) -> cons(recip(sqr(N)))
1093.07/291.62	sqr(0') -> 0'
1093.07/291.62	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.62	dbl(0') -> 0'
1093.07/291.62	dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.62	add(0', X) -> X
1093.07/291.62	add(s(X), Y) -> s(add(X, Y))
1093.07/291.62	first(0', X) -> nil
1093.07/291.62	first(s(X), cons(Y)) -> cons(Y)
1093.07/291.62	half(0') -> 0'
1093.07/291.62	half(s(0')) -> 0'
1093.07/291.62	half(s(s(X))) -> s(half(X))
1093.07/291.62	half(dbl(X)) -> X
1093.07/291.62	
1093.07/291.62	Types:
1093.07/291.62	terms :: 0':s -> cons:nil
1093.07/291.62	cons :: recip -> cons:nil
1093.07/291.62	recip :: 0':s -> recip
1093.07/291.62	sqr :: 0':s -> 0':s
1093.07/291.62	0' :: 0':s
1093.07/291.62	s :: 0':s -> 0':s
1093.07/291.62	add :: 0':s -> 0':s -> 0':s
1093.07/291.62	dbl :: 0':s -> 0':s
1093.07/291.62	first :: 0':s -> cons:nil -> cons:nil
1093.07/291.62	nil :: cons:nil
1093.07/291.62	half :: 0':s -> 0':s
1093.07/291.62	hole_cons:nil1_0 :: cons:nil
1093.07/291.62	hole_0':s2_0 :: 0':s
1093.07/291.62	hole_recip3_0 :: recip
1093.07/291.62	gen_0':s4_0 :: Nat -> 0':s
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(61) OrderProof (LOWER BOUND(ID))
1093.07/291.62	Heuristically decided to analyse the following defined symbols:
1093.07/291.62	sqr, add, dbl, half
1093.07/291.62	
1093.07/291.62	They will be analysed ascendingly in the following order:
1093.07/291.62	add < sqr
1093.07/291.62	dbl < sqr
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(62)
1093.07/291.62	Obligation:
1093.07/291.62	TRS:
1093.07/291.62	Rules:
1093.07/291.62	terms(N) -> cons(recip(sqr(N)))
1093.07/291.62	sqr(0') -> 0'
1093.07/291.62	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.62	dbl(0') -> 0'
1093.07/291.62	dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.62	add(0', X) -> X
1093.07/291.62	add(s(X), Y) -> s(add(X, Y))
1093.07/291.62	first(0', X) -> nil
1093.07/291.62	first(s(X), cons(Y)) -> cons(Y)
1093.07/291.62	half(0') -> 0'
1093.07/291.62	half(s(0')) -> 0'
1093.07/291.62	half(s(s(X))) -> s(half(X))
1093.07/291.62	half(dbl(X)) -> X
1093.07/291.62	
1093.07/291.62	Types:
1093.07/291.62	terms :: 0':s -> cons:nil
1093.07/291.62	cons :: recip -> cons:nil
1093.07/291.62	recip :: 0':s -> recip
1093.07/291.62	sqr :: 0':s -> 0':s
1093.07/291.62	0' :: 0':s
1093.07/291.62	s :: 0':s -> 0':s
1093.07/291.62	add :: 0':s -> 0':s -> 0':s
1093.07/291.62	dbl :: 0':s -> 0':s
1093.07/291.62	first :: 0':s -> cons:nil -> cons:nil
1093.07/291.62	nil :: cons:nil
1093.07/291.62	half :: 0':s -> 0':s
1093.07/291.62	hole_cons:nil1_0 :: cons:nil
1093.07/291.62	hole_0':s2_0 :: 0':s
1093.07/291.62	hole_recip3_0 :: recip
1093.07/291.62	gen_0':s4_0 :: Nat -> 0':s
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Generator Equations:
1093.07/291.62	gen_0':s4_0(0) <=> 0'
1093.07/291.62	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	The following defined symbols remain to be analysed:
1093.07/291.62	add, sqr, dbl, half
1093.07/291.62	
1093.07/291.62	They will be analysed ascendingly in the following order:
1093.07/291.62	add < sqr
1093.07/291.62	dbl < sqr
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(63) RewriteLemmaProof (LOWER BOUND(ID))
1093.07/291.62	Proved the following rewrite lemma:
1093.07/291.62	add(gen_0':s4_0(n6_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n6_0, b)), rt in Omega(1 + n6_0)
1093.07/291.62	
1093.07/291.62	Induction Base:
1093.07/291.62	add(gen_0':s4_0(0), gen_0':s4_0(b)) ->_R^Omega(1)
1093.07/291.62	gen_0':s4_0(b)
1093.07/291.62	
1093.07/291.62	Induction Step:
1093.07/291.62	add(gen_0':s4_0(+(n6_0, 1)), gen_0':s4_0(b)) ->_R^Omega(1)
1093.07/291.62	s(add(gen_0':s4_0(n6_0), gen_0':s4_0(b))) ->_IH
1093.07/291.62	s(gen_0':s4_0(+(b, c7_0)))
1093.07/291.62	
1093.07/291.62	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(64)
1093.07/291.62	Complex Obligation (BEST)
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(65)
1093.07/291.62	Obligation:
1093.07/291.62	Proved the lower bound n^1 for the following obligation:
1093.07/291.62	
1093.07/291.62	TRS:
1093.07/291.62	Rules:
1093.07/291.62	terms(N) -> cons(recip(sqr(N)))
1093.07/291.62	sqr(0') -> 0'
1093.07/291.62	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.62	dbl(0') -> 0'
1093.07/291.62	dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.62	add(0', X) -> X
1093.07/291.62	add(s(X), Y) -> s(add(X, Y))
1093.07/291.62	first(0', X) -> nil
1093.07/291.62	first(s(X), cons(Y)) -> cons(Y)
1093.07/291.62	half(0') -> 0'
1093.07/291.62	half(s(0')) -> 0'
1093.07/291.62	half(s(s(X))) -> s(half(X))
1093.07/291.62	half(dbl(X)) -> X
1093.07/291.62	
1093.07/291.62	Types:
1093.07/291.62	terms :: 0':s -> cons:nil
1093.07/291.62	cons :: recip -> cons:nil
1093.07/291.62	recip :: 0':s -> recip
1093.07/291.62	sqr :: 0':s -> 0':s
1093.07/291.62	0' :: 0':s
1093.07/291.62	s :: 0':s -> 0':s
1093.07/291.62	add :: 0':s -> 0':s -> 0':s
1093.07/291.62	dbl :: 0':s -> 0':s
1093.07/291.62	first :: 0':s -> cons:nil -> cons:nil
1093.07/291.62	nil :: cons:nil
1093.07/291.62	half :: 0':s -> 0':s
1093.07/291.62	hole_cons:nil1_0 :: cons:nil
1093.07/291.62	hole_0':s2_0 :: 0':s
1093.07/291.62	hole_recip3_0 :: recip
1093.07/291.62	gen_0':s4_0 :: Nat -> 0':s
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Generator Equations:
1093.07/291.62	gen_0':s4_0(0) <=> 0'
1093.07/291.62	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	The following defined symbols remain to be analysed:
1093.07/291.62	add, sqr, dbl, half
1093.07/291.62	
1093.07/291.62	They will be analysed ascendingly in the following order:
1093.07/291.62	add < sqr
1093.07/291.62	dbl < sqr
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(66) LowerBoundPropagationProof (FINISHED)
1093.07/291.62	Propagated lower bound.
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(67)
1093.07/291.62	BOUNDS(n^1, INF)
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(68)
1093.07/291.62	Obligation:
1093.07/291.62	TRS:
1093.07/291.62	Rules:
1093.07/291.62	terms(N) -> cons(recip(sqr(N)))
1093.07/291.62	sqr(0') -> 0'
1093.07/291.62	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.62	dbl(0') -> 0'
1093.07/291.62	dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.62	add(0', X) -> X
1093.07/291.62	add(s(X), Y) -> s(add(X, Y))
1093.07/291.62	first(0', X) -> nil
1093.07/291.62	first(s(X), cons(Y)) -> cons(Y)
1093.07/291.62	half(0') -> 0'
1093.07/291.62	half(s(0')) -> 0'
1093.07/291.62	half(s(s(X))) -> s(half(X))
1093.07/291.62	half(dbl(X)) -> X
1093.07/291.62	
1093.07/291.62	Types:
1093.07/291.62	terms :: 0':s -> cons:nil
1093.07/291.62	cons :: recip -> cons:nil
1093.07/291.62	recip :: 0':s -> recip
1093.07/291.62	sqr :: 0':s -> 0':s
1093.07/291.62	0' :: 0':s
1093.07/291.62	s :: 0':s -> 0':s
1093.07/291.62	add :: 0':s -> 0':s -> 0':s
1093.07/291.62	dbl :: 0':s -> 0':s
1093.07/291.62	first :: 0':s -> cons:nil -> cons:nil
1093.07/291.62	nil :: cons:nil
1093.07/291.62	half :: 0':s -> 0':s
1093.07/291.62	hole_cons:nil1_0 :: cons:nil
1093.07/291.62	hole_0':s2_0 :: 0':s
1093.07/291.62	hole_recip3_0 :: recip
1093.07/291.62	gen_0':s4_0 :: Nat -> 0':s
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Lemmas:
1093.07/291.62	add(gen_0':s4_0(n6_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n6_0, b)), rt in Omega(1 + n6_0)
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Generator Equations:
1093.07/291.62	gen_0':s4_0(0) <=> 0'
1093.07/291.62	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	The following defined symbols remain to be analysed:
1093.07/291.62	dbl, sqr, half
1093.07/291.62	
1093.07/291.62	They will be analysed ascendingly in the following order:
1093.07/291.62	dbl < sqr
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(69) RewriteLemmaProof (LOWER BOUND(ID))
1093.07/291.62	Proved the following rewrite lemma:
1093.07/291.62	dbl(gen_0':s4_0(n567_0)) -> gen_0':s4_0(*(2, n567_0)), rt in Omega(1 + n567_0)
1093.07/291.62	
1093.07/291.62	Induction Base:
1093.07/291.62	dbl(gen_0':s4_0(0)) ->_R^Omega(1)
1093.07/291.62	0'
1093.07/291.62	
1093.07/291.62	Induction Step:
1093.07/291.62	dbl(gen_0':s4_0(+(n567_0, 1))) ->_R^Omega(1)
1093.07/291.62	s(s(dbl(gen_0':s4_0(n567_0)))) ->_IH
1093.07/291.62	s(s(gen_0':s4_0(*(2, c568_0))))
1093.07/291.62	
1093.07/291.62	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(70)
1093.07/291.62	Obligation:
1093.07/291.62	TRS:
1093.07/291.62	Rules:
1093.07/291.62	terms(N) -> cons(recip(sqr(N)))
1093.07/291.62	sqr(0') -> 0'
1093.07/291.62	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.62	dbl(0') -> 0'
1093.07/291.62	dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.62	add(0', X) -> X
1093.07/291.62	add(s(X), Y) -> s(add(X, Y))
1093.07/291.62	first(0', X) -> nil
1093.07/291.62	first(s(X), cons(Y)) -> cons(Y)
1093.07/291.62	half(0') -> 0'
1093.07/291.62	half(s(0')) -> 0'
1093.07/291.62	half(s(s(X))) -> s(half(X))
1093.07/291.62	half(dbl(X)) -> X
1093.07/291.62	
1093.07/291.62	Types:
1093.07/291.62	terms :: 0':s -> cons:nil
1093.07/291.62	cons :: recip -> cons:nil
1093.07/291.62	recip :: 0':s -> recip
1093.07/291.62	sqr :: 0':s -> 0':s
1093.07/291.62	0' :: 0':s
1093.07/291.62	s :: 0':s -> 0':s
1093.07/291.62	add :: 0':s -> 0':s -> 0':s
1093.07/291.62	dbl :: 0':s -> 0':s
1093.07/291.62	first :: 0':s -> cons:nil -> cons:nil
1093.07/291.62	nil :: cons:nil
1093.07/291.62	half :: 0':s -> 0':s
1093.07/291.62	hole_cons:nil1_0 :: cons:nil
1093.07/291.62	hole_0':s2_0 :: 0':s
1093.07/291.62	hole_recip3_0 :: recip
1093.07/291.62	gen_0':s4_0 :: Nat -> 0':s
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Lemmas:
1093.07/291.62	add(gen_0':s4_0(n6_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n6_0, b)), rt in Omega(1 + n6_0)
1093.07/291.62	dbl(gen_0':s4_0(n567_0)) -> gen_0':s4_0(*(2, n567_0)), rt in Omega(1 + n567_0)
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Generator Equations:
1093.07/291.62	gen_0':s4_0(0) <=> 0'
1093.07/291.62	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	The following defined symbols remain to be analysed:
1093.07/291.62	sqr, half
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(71) RewriteLemmaProof (LOWER BOUND(ID))
1093.07/291.62	Proved the following rewrite lemma:
1093.07/291.62	sqr(gen_0':s4_0(n827_0)) -> gen_0':s4_0(*(n827_0, n827_0)), rt in Omega(1 + n827_0 + n827_0^2 + n827_0^3)
1093.07/291.62	
1093.07/291.62	Induction Base:
1093.07/291.62	sqr(gen_0':s4_0(0)) ->_R^Omega(1)
1093.07/291.62	0'
1093.07/291.62	
1093.07/291.62	Induction Step:
1093.07/291.62	sqr(gen_0':s4_0(+(n827_0, 1))) ->_R^Omega(1)
1093.07/291.62	s(add(sqr(gen_0':s4_0(n827_0)), dbl(gen_0':s4_0(n827_0)))) ->_IH
1093.07/291.62	s(add(gen_0':s4_0(*(c828_0, c828_0)), dbl(gen_0':s4_0(n827_0)))) ->_L^Omega(1 + n827_0)
1093.07/291.62	s(add(gen_0':s4_0(*(n827_0, n827_0)), gen_0':s4_0(*(2, n827_0)))) ->_L^Omega(1 + n827_0^2)
1093.07/291.62	s(gen_0':s4_0(+(*(n827_0, n827_0), *(2, n827_0))))
1093.07/291.62	
1093.07/291.62	We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3).
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(72)
1093.07/291.62	Complex Obligation (BEST)
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(73)
1093.07/291.62	Obligation:
1093.07/291.62	Proved the lower bound n^3 for the following obligation:
1093.07/291.62	
1093.07/291.62	TRS:
1093.07/291.62	Rules:
1093.07/291.62	terms(N) -> cons(recip(sqr(N)))
1093.07/291.62	sqr(0') -> 0'
1093.07/291.62	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.62	dbl(0') -> 0'
1093.07/291.62	dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.62	add(0', X) -> X
1093.07/291.62	add(s(X), Y) -> s(add(X, Y))
1093.07/291.62	first(0', X) -> nil
1093.07/291.62	first(s(X), cons(Y)) -> cons(Y)
1093.07/291.62	half(0') -> 0'
1093.07/291.62	half(s(0')) -> 0'
1093.07/291.62	half(s(s(X))) -> s(half(X))
1093.07/291.62	half(dbl(X)) -> X
1093.07/291.62	
1093.07/291.62	Types:
1093.07/291.62	terms :: 0':s -> cons:nil
1093.07/291.62	cons :: recip -> cons:nil
1093.07/291.62	recip :: 0':s -> recip
1093.07/291.62	sqr :: 0':s -> 0':s
1093.07/291.62	0' :: 0':s
1093.07/291.62	s :: 0':s -> 0':s
1093.07/291.62	add :: 0':s -> 0':s -> 0':s
1093.07/291.62	dbl :: 0':s -> 0':s
1093.07/291.62	first :: 0':s -> cons:nil -> cons:nil
1093.07/291.62	nil :: cons:nil
1093.07/291.62	half :: 0':s -> 0':s
1093.07/291.62	hole_cons:nil1_0 :: cons:nil
1093.07/291.62	hole_0':s2_0 :: 0':s
1093.07/291.62	hole_recip3_0 :: recip
1093.07/291.62	gen_0':s4_0 :: Nat -> 0':s
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Lemmas:
1093.07/291.62	add(gen_0':s4_0(n6_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n6_0, b)), rt in Omega(1 + n6_0)
1093.07/291.62	dbl(gen_0':s4_0(n567_0)) -> gen_0':s4_0(*(2, n567_0)), rt in Omega(1 + n567_0)
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Generator Equations:
1093.07/291.62	gen_0':s4_0(0) <=> 0'
1093.07/291.62	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	The following defined symbols remain to be analysed:
1093.07/291.62	sqr, half
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(74) LowerBoundPropagationProof (FINISHED)
1093.07/291.62	Propagated lower bound.
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(75)
1093.07/291.62	BOUNDS(n^3, INF)
1093.07/291.62	
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(76)
1093.07/291.62	Obligation:
1093.07/291.62	TRS:
1093.07/291.62	Rules:
1093.07/291.62	terms(N) -> cons(recip(sqr(N)))
1093.07/291.62	sqr(0') -> 0'
1093.07/291.62	sqr(s(X)) -> s(add(sqr(X), dbl(X)))
1093.07/291.62	dbl(0') -> 0'
1093.07/291.62	dbl(s(X)) -> s(s(dbl(X)))
1093.07/291.62	add(0', X) -> X
1093.07/291.62	add(s(X), Y) -> s(add(X, Y))
1093.07/291.62	first(0', X) -> nil
1093.07/291.62	first(s(X), cons(Y)) -> cons(Y)
1093.07/291.62	half(0') -> 0'
1093.07/291.62	half(s(0')) -> 0'
1093.07/291.62	half(s(s(X))) -> s(half(X))
1093.07/291.62	half(dbl(X)) -> X
1093.07/291.62	
1093.07/291.62	Types:
1093.07/291.62	terms :: 0':s -> cons:nil
1093.07/291.62	cons :: recip -> cons:nil
1093.07/291.62	recip :: 0':s -> recip
1093.07/291.62	sqr :: 0':s -> 0':s
1093.07/291.62	0' :: 0':s
1093.07/291.62	s :: 0':s -> 0':s
1093.07/291.62	add :: 0':s -> 0':s -> 0':s
1093.07/291.62	dbl :: 0':s -> 0':s
1093.07/291.62	first :: 0':s -> cons:nil -> cons:nil
1093.07/291.62	nil :: cons:nil
1093.07/291.62	half :: 0':s -> 0':s
1093.07/291.62	hole_cons:nil1_0 :: cons:nil
1093.07/291.62	hole_0':s2_0 :: 0':s
1093.07/291.62	hole_recip3_0 :: recip
1093.07/291.62	gen_0':s4_0 :: Nat -> 0':s
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Lemmas:
1093.07/291.62	add(gen_0':s4_0(n6_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n6_0, b)), rt in Omega(1 + n6_0)
1093.07/291.62	dbl(gen_0':s4_0(n567_0)) -> gen_0':s4_0(*(2, n567_0)), rt in Omega(1 + n567_0)
1093.07/291.62	sqr(gen_0':s4_0(n827_0)) -> gen_0':s4_0(*(n827_0, n827_0)), rt in Omega(1 + n827_0 + n827_0^2 + n827_0^3)
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	Generator Equations:
1093.07/291.62	gen_0':s4_0(0) <=> 0'
1093.07/291.62	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1093.07/291.62	
1093.07/291.62	
1093.07/291.62	The following defined symbols remain to be analysed:
1093.07/291.62	half
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(77) RewriteLemmaProof (LOWER BOUND(ID))
1093.07/291.62	Proved the following rewrite lemma:
1093.07/291.62	half(gen_0':s4_0(*(2, n1160_0))) -> gen_0':s4_0(n1160_0), rt in Omega(1 + n1160_0)
1093.07/291.62	
1093.07/291.62	Induction Base:
1093.07/291.62	half(gen_0':s4_0(*(2, 0))) ->_R^Omega(1)
1093.07/291.62	0'
1093.07/291.62	
1093.07/291.62	Induction Step:
1093.07/291.62	half(gen_0':s4_0(*(2, +(n1160_0, 1)))) ->_R^Omega(1)
1093.07/291.62	s(half(gen_0':s4_0(*(2, n1160_0)))) ->_IH
1093.07/291.62	s(gen_0':s4_0(c1161_0))
1093.07/291.62	
1093.07/291.62	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1093.07/291.62	----------------------------------------
1093.07/291.62	
1093.07/291.62	(78)
1093.07/291.62	BOUNDS(1, INF)
1093.26/291.72	EOF