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