28.39/9.59	WORST_CASE(Omega(n^3), O(n^3))
28.71/10.27	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
28.71/10.27	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
28.71/10.27	
28.71/10.27	
28.71/10.27	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3).
28.71/10.27	
28.71/10.27	(0) CpxTRS
28.71/10.27	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
28.71/10.27	(2) CpxWeightedTrs
28.71/10.27	    (3) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
28.71/10.27	    (4) CpxWeightedTrs
28.71/10.27	    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
28.71/10.27	    (6) CpxTypedWeightedTrs
28.71/10.27	    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
28.71/10.27	    (8) CpxTypedWeightedCompleteTrs
28.71/10.27	    (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
28.71/10.27	    (10) CpxTypedWeightedCompleteTrs
28.71/10.27	    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
28.71/10.27	    (12) CpxRNTS
28.71/10.27	    (13) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
28.71/10.27	    (14) CpxRNTS
28.71/10.27	    (15) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
28.71/10.27	    (16) CpxRNTS
28.71/10.27	    (17) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
28.71/10.27	    (18) CpxRNTS
28.71/10.27	    (19) IntTrsBoundProof [UPPER BOUND(ID), 146 ms]
28.71/10.27	    (20) CpxRNTS
28.71/10.27	    (21) IntTrsBoundProof [UPPER BOUND(ID), 117 ms]
28.71/10.27	    (22) CpxRNTS
28.71/10.27	    (23) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
28.71/10.27	    (24) CpxRNTS
28.71/10.27	    (25) IntTrsBoundProof [UPPER BOUND(ID), 340 ms]
28.71/10.27	    (26) CpxRNTS
28.71/10.27	    (27) IntTrsBoundProof [UPPER BOUND(ID), 84 ms]
28.71/10.27	    (28) CpxRNTS
28.71/10.27	    (29) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
28.71/10.27	    (30) CpxRNTS
28.71/10.27	    (31) IntTrsBoundProof [UPPER BOUND(ID), 1675 ms]
28.71/10.27	    (32) CpxRNTS
28.71/10.27	    (33) IntTrsBoundProof [UPPER BOUND(ID), 169 ms]
28.71/10.27	    (34) CpxRNTS
28.71/10.27	    (35) FinalProof [FINISHED, 0 ms]
28.71/10.27	    (36) BOUNDS(1, n^3)
28.71/10.27	(37) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
28.71/10.27	(38) CpxTRS
28.71/10.27	    (39) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
28.71/10.27	    (40) typed CpxTrs
28.71/10.27	    (41) OrderProof [LOWER BOUND(ID), 0 ms]
28.71/10.27	    (42) typed CpxTrs
28.71/10.27	    (43) RewriteLemmaProof [LOWER BOUND(ID), 317 ms]
28.71/10.27	    (44) BEST
28.71/10.27	        (45) proven lower bound
28.71/10.27	            (46) LowerBoundPropagationProof [FINISHED, 0 ms]
28.71/10.27	            (47) BOUNDS(n^1, INF)
28.71/10.27	        (48) typed CpxTrs
28.71/10.27	            (49) RewriteLemmaProof [LOWER BOUND(ID), 1769 ms]
28.71/10.27	            (50) typed CpxTrs
28.71/10.27	            (51) RewriteLemmaProof [LOWER BOUND(ID), 47 ms]
28.71/10.27	            (52) proven lower bound
28.71/10.27	            (53) LowerBoundPropagationProof [FINISHED, 0 ms]
28.71/10.27	            (54) BOUNDS(n^3, INF)
28.71/10.27	
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(0)
28.71/10.27	Obligation:
28.71/10.27	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, n^3).
28.71/10.27	
28.71/10.27	
28.71/10.27	The TRS R consists of the following rules:
28.71/10.27	
28.71/10.27	   +(0, y) -> y
28.71/10.27	   +(s(x), y) -> s(+(x, y))
28.71/10.27	   +(p(x), y) -> p(+(x, y))
28.71/10.27	   minus(0) -> 0
28.71/10.27	   minus(s(x)) -> p(minus(x))
28.71/10.27	   minus(p(x)) -> s(minus(x))
28.71/10.27	   *(0, y) -> 0
28.71/10.27	   *(s(x), y) -> +(*(x, y), y)
28.71/10.27	   *(p(x), y) -> +(*(x, y), minus(y))
28.71/10.27	
28.71/10.27	S is empty.
28.71/10.27	Rewrite Strategy: INNERMOST
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
28.71/10.27	Transformed relative TRS to weighted TRS
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(2)
28.71/10.27	Obligation:
28.71/10.27	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3).
28.71/10.27	
28.71/10.27	
28.71/10.27	The TRS R consists of the following rules:
28.71/10.27	
28.71/10.27	   +(0, y) -> y [1]
28.71/10.27	   +(s(x), y) -> s(+(x, y)) [1]
28.71/10.27	   +(p(x), y) -> p(+(x, y)) [1]
28.71/10.27	   minus(0) -> 0 [1]
28.71/10.27	   minus(s(x)) -> p(minus(x)) [1]
28.71/10.27	   minus(p(x)) -> s(minus(x)) [1]
28.71/10.27	   *(0, y) -> 0 [1]
28.71/10.27	   *(s(x), y) -> +(*(x, y), y) [1]
28.71/10.27	   *(p(x), y) -> +(*(x, y), minus(y)) [1]
28.71/10.27	
28.71/10.27	Rewrite Strategy: INNERMOST
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(3) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
28.71/10.27	Renamed defined symbols to avoid conflicts with arithmetic symbols:
28.71/10.27	
28.71/10.27	+ => plus
28.71/10.27	* => times
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(4)
28.71/10.27	Obligation:
28.71/10.27	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3).
28.71/10.27	
28.71/10.27	
28.71/10.27	The TRS R consists of the following rules:
28.71/10.27	
28.71/10.27	   plus(0, y) -> y [1]
28.71/10.27	   plus(s(x), y) -> s(plus(x, y)) [1]
28.71/10.27	   plus(p(x), y) -> p(plus(x, y)) [1]
28.71/10.27	   minus(0) -> 0 [1]
28.71/10.27	   minus(s(x)) -> p(minus(x)) [1]
28.71/10.27	   minus(p(x)) -> s(minus(x)) [1]
28.71/10.27	   times(0, y) -> 0 [1]
28.71/10.27	   times(s(x), y) -> plus(times(x, y), y) [1]
28.71/10.27	   times(p(x), y) -> plus(times(x, y), minus(y)) [1]
28.71/10.27	
28.71/10.27	Rewrite Strategy: INNERMOST
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(5) TypeInferenceProof (BOTH BOUNDS(ID, ID))
28.71/10.27	Infered types.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(6)
28.71/10.27	Obligation:
28.71/10.27	Runtime Complexity Weighted TRS with Types.
28.71/10.27	The TRS R consists of the following rules:
28.71/10.27	
28.71/10.27	   plus(0, y) -> y [1]
28.71/10.27	   plus(s(x), y) -> s(plus(x, y)) [1]
28.71/10.27	   plus(p(x), y) -> p(plus(x, y)) [1]
28.71/10.27	   minus(0) -> 0 [1]
28.71/10.27	   minus(s(x)) -> p(minus(x)) [1]
28.71/10.27	   minus(p(x)) -> s(minus(x)) [1]
28.71/10.27	   times(0, y) -> 0 [1]
28.71/10.27	   times(s(x), y) -> plus(times(x, y), y) [1]
28.71/10.27	   times(p(x), y) -> plus(times(x, y), minus(y)) [1]
28.71/10.27	
28.71/10.27	The TRS has the following type information:
28.71/10.27	plus :: 0:s:p -> 0:s:p -> 0:s:p
28.71/10.27	0 :: 0:s:p
28.71/10.27	s :: 0:s:p -> 0:s:p
28.71/10.27	p :: 0:s:p -> 0:s:p
28.71/10.27	minus :: 0:s:p -> 0:s:p
28.71/10.27	times :: 0:s:p -> 0:s:p -> 0:s:p
28.71/10.27	
28.71/10.27	Rewrite Strategy: INNERMOST
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(7) CompletionProof (UPPER BOUND(ID))
28.71/10.27	The transformation into a RNTS is sound, since:
28.71/10.27	
28.71/10.27	(a) The obligation is a constructor system where every type has a constant constructor,
28.71/10.27	
28.71/10.27	(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
28.71/10.27	none
28.71/10.27	
28.71/10.27	(c) The following functions are completely defined:
28.71/10.27	
28.71/10.27	   times_2
28.71/10.27	   minus_1
28.71/10.27	   plus_2
28.71/10.27	
28.71/10.27	Due to the following rules being added:
28.71/10.27	none
28.71/10.27	
28.71/10.27	And the following fresh constants: none
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(8)
28.71/10.27	Obligation:
28.71/10.27	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
28.71/10.27	
28.71/10.27	Runtime Complexity Weighted TRS with Types.
28.71/10.27	The TRS R consists of the following rules:
28.71/10.27	
28.71/10.27	   plus(0, y) -> y [1]
28.71/10.27	   plus(s(x), y) -> s(plus(x, y)) [1]
28.71/10.27	   plus(p(x), y) -> p(plus(x, y)) [1]
28.71/10.27	   minus(0) -> 0 [1]
28.71/10.27	   minus(s(x)) -> p(minus(x)) [1]
28.71/10.27	   minus(p(x)) -> s(minus(x)) [1]
28.71/10.27	   times(0, y) -> 0 [1]
28.71/10.27	   times(s(x), y) -> plus(times(x, y), y) [1]
28.71/10.27	   times(p(x), y) -> plus(times(x, y), minus(y)) [1]
28.71/10.27	
28.71/10.27	The TRS has the following type information:
28.71/10.27	plus :: 0:s:p -> 0:s:p -> 0:s:p
28.71/10.27	0 :: 0:s:p
28.71/10.27	s :: 0:s:p -> 0:s:p
28.71/10.27	p :: 0:s:p -> 0:s:p
28.71/10.27	minus :: 0:s:p -> 0:s:p
28.71/10.27	times :: 0:s:p -> 0:s:p -> 0:s:p
28.71/10.27	
28.71/10.27	Rewrite Strategy: INNERMOST
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(9) NarrowingProof (BOTH BOUNDS(ID, ID))
28.71/10.27	Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(10)
28.71/10.27	Obligation:
28.71/10.27	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
28.71/10.27	
28.71/10.27	Runtime Complexity Weighted TRS with Types.
28.71/10.27	The TRS R consists of the following rules:
28.71/10.27	
28.71/10.27	   plus(0, y) -> y [1]
28.71/10.27	   plus(s(x), y) -> s(plus(x, y)) [1]
28.71/10.27	   plus(p(x), y) -> p(plus(x, y)) [1]
28.71/10.27	   minus(0) -> 0 [1]
28.71/10.27	   minus(s(x)) -> p(minus(x)) [1]
28.71/10.27	   minus(p(x)) -> s(minus(x)) [1]
28.71/10.27	   times(0, y) -> 0 [1]
28.71/10.27	   times(s(0), y) -> plus(0, y) [2]
28.71/10.27	   times(s(s(x')), y) -> plus(plus(times(x', y), y), y) [2]
28.71/10.27	   times(s(p(x'')), y) -> plus(plus(times(x'', y), minus(y)), y) [2]
28.71/10.27	   times(p(0), 0) -> plus(0, 0) [3]
28.71/10.27	   times(p(0), s(x3)) -> plus(0, p(minus(x3))) [3]
28.71/10.27	   times(p(0), p(x4)) -> plus(0, s(minus(x4))) [3]
28.71/10.27	   times(p(s(x1)), 0) -> plus(plus(times(x1, 0), 0), 0) [3]
28.71/10.27	   times(p(s(x1)), s(x5)) -> plus(plus(times(x1, s(x5)), s(x5)), p(minus(x5))) [3]
28.71/10.27	   times(p(s(x1)), p(x6)) -> plus(plus(times(x1, p(x6)), p(x6)), s(minus(x6))) [3]
28.71/10.27	   times(p(p(x2)), 0) -> plus(plus(times(x2, 0), minus(0)), 0) [3]
28.71/10.27	   times(p(p(x2)), s(x7)) -> plus(plus(times(x2, s(x7)), minus(s(x7))), p(minus(x7))) [3]
28.71/10.27	   times(p(p(x2)), p(x8)) -> plus(plus(times(x2, p(x8)), minus(p(x8))), s(minus(x8))) [3]
28.71/10.27	
28.71/10.27	The TRS has the following type information:
28.71/10.27	plus :: 0:s:p -> 0:s:p -> 0:s:p
28.71/10.27	0 :: 0:s:p
28.71/10.27	s :: 0:s:p -> 0:s:p
28.71/10.27	p :: 0:s:p -> 0:s:p
28.71/10.27	minus :: 0:s:p -> 0:s:p
28.71/10.27	times :: 0:s:p -> 0:s:p -> 0:s:p
28.71/10.27	
28.71/10.27	Rewrite Strategy: INNERMOST
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
28.71/10.27	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
28.71/10.27	The constant constructors are abstracted as follows:
28.71/10.27	
28.71/10.27	   0 => 0
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(12)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 }-> 1 + minus(x) :|: x >= 0, z = 1 + x
28.71/10.27	   plus(z, z') -{ 1 }-> y :|: y >= 0, z = 0, z' = y
28.71/10.27	   plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(x', y), y), y) :|: x' >= 0, y >= 0, z = 1 + (1 + x'), z' = y
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(x'', y), minus(y)), y) :|: y >= 0, x'' >= 0, z = 1 + (1 + x''), z' = y
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(x1, 0), 0), 0) :|: z = 1 + (1 + x1), x1 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(x1, 1 + x5), 1 + x5), 1 + minus(x5)) :|: z = 1 + (1 + x1), x1 >= 0, x5 >= 0, z' = 1 + x5
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(x1, 1 + x6), 1 + x6), 1 + minus(x6)) :|: z' = 1 + x6, z = 1 + (1 + x1), x1 >= 0, x6 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(x2, 0), minus(0)), 0) :|: z = 1 + (1 + x2), x2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(x2, 1 + x7), minus(1 + x7)), 1 + minus(x7)) :|: z' = 1 + x7, z = 1 + (1 + x2), x7 >= 0, x2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(x2, 1 + x8), minus(1 + x8)), 1 + minus(x8)) :|: z = 1 + (1 + x2), z' = 1 + x8, x8 >= 0, x2 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(0, y) :|: z = 1 + 0, y >= 0, z' = y
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 0) :|: z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 1 + minus(x3)) :|: z' = 1 + x3, z = 1 + 0, x3 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 1 + minus(x4)) :|: x4 >= 0, z = 1 + 0, z' = 1 + x4
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y
28.71/10.27	
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(13) SimplificationProof (BOTH BOUNDS(ID, ID))
28.71/10.27	Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(14)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 }-> 1 + minus(z - 1) :|: z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 }-> 1 + plus(z - 1, z') :|: z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), minus(z')), z') :|: z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), minus(0)), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), minus(1 + (z' - 1))), 1 + minus(z' - 1)) :|: z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + minus(z' - 1)) :|: z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(0, z') :|: z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 0) :|: z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 1 + minus(z' - 1)) :|: z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(15) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
28.71/10.27	Found the following analysis order by SCC decomposition:
28.71/10.27	
28.71/10.27	   { minus }
28.71/10.27	   { plus }
28.71/10.27	   { times }
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(16)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 }-> 1 + minus(z - 1) :|: z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 }-> 1 + plus(z - 1, z') :|: z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), minus(z')), z') :|: z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), minus(0)), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), minus(1 + (z' - 1))), 1 + minus(z' - 1)) :|: z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + minus(z' - 1)) :|: z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(0, z') :|: z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 0) :|: z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 1 + minus(z' - 1)) :|: z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: {minus}, {plus}, {times}
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(17) ResultPropagationProof (UPPER BOUND(ID))
28.71/10.27	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(18)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 }-> 1 + minus(z - 1) :|: z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 }-> 1 + plus(z - 1, z') :|: z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), minus(z')), z') :|: z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), minus(0)), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), minus(1 + (z' - 1))), 1 + minus(z' - 1)) :|: z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + minus(z' - 1)) :|: z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(0, z') :|: z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 0) :|: z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 1 + minus(z' - 1)) :|: z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: {minus}, {plus}, {times}
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(19) IntTrsBoundProof (UPPER BOUND(ID))
28.71/10.27	
28.71/10.27	Computed SIZE bound using CoFloCo for: minus
28.71/10.27	after applying outer abstraction to obtain an ITS,
28.71/10.27	resulting in: O(n^1) with polynomial bound: z
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(20)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 }-> 1 + minus(z - 1) :|: z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 }-> 1 + plus(z - 1, z') :|: z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), minus(z')), z') :|: z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), minus(0)), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), minus(1 + (z' - 1))), 1 + minus(z' - 1)) :|: z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + minus(z' - 1)) :|: z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(0, z') :|: z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 0) :|: z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 1 + minus(z' - 1)) :|: z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: {minus}, {plus}, {times}
28.71/10.27	Previous analysis results are:
28.71/10.27	  minus: runtime: ?, size: O(n^1) [z]
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(21) IntTrsBoundProof (UPPER BOUND(ID))
28.71/10.27	
28.71/10.27	Computed RUNTIME bound using CoFloCo for: minus
28.71/10.27	after applying outer abstraction to obtain an ITS,
28.71/10.27	resulting in: O(n^1) with polynomial bound: 1 + z
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(22)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 }-> 1 + minus(z - 1) :|: z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 }-> 1 + plus(z - 1, z') :|: z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), minus(z')), z') :|: z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), minus(0)), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), minus(1 + (z' - 1))), 1 + minus(z' - 1)) :|: z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + minus(z' - 1)) :|: z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(0, z') :|: z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 0) :|: z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 1 + minus(z' - 1)) :|: z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: {plus}, {times}
28.71/10.27	Previous analysis results are:
28.71/10.27	  minus: runtime: O(n^1) [1 + z], size: O(n^1) [z]
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(23) ResultPropagationProof (UPPER BOUND(ID))
28.71/10.27	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(24)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 }-> 1 + plus(z - 1, z') :|: z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, z'), s'), z') :|: s' >= 0, s' <= z', z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 4 }-> plus(plus(times(z - 2, 0), s2), 0) :|: s2 >= 0, s2 <= 0, z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 4 + 2*z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), s3), 1 + s4) :|: s3 >= 0, s3 <= 1 + (z' - 1), s4 >= 0, s4 <= z' - 1, z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(0, z') :|: z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 0) :|: z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(0, 1 + s'') :|: s'' >= 0, s'' <= z' - 1, z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: {plus}, {times}
28.71/10.27	Previous analysis results are:
28.71/10.27	  minus: runtime: O(n^1) [1 + z], size: O(n^1) [z]
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(25) IntTrsBoundProof (UPPER BOUND(ID))
28.71/10.27	
28.71/10.27	Computed SIZE bound using CoFloCo for: plus
28.71/10.27	after applying outer abstraction to obtain an ITS,
28.71/10.27	resulting in: O(n^1) with polynomial bound: z + z'
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(26)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 }-> 1 + plus(z - 1, z') :|: z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, z'), s'), z') :|: s' >= 0, s' <= z', z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 4 }-> plus(plus(times(z - 2, 0), s2), 0) :|: s2 >= 0, s2 <= 0, z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 4 + 2*z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), s3), 1 + s4) :|: s3 >= 0, s3 <= 1 + (z' - 1), s4 >= 0, s4 <= z' - 1, z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(0, z') :|: z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 0) :|: z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(0, 1 + s'') :|: s'' >= 0, s'' <= z' - 1, z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: {plus}, {times}
28.71/10.27	Previous analysis results are:
28.71/10.27	  minus: runtime: O(n^1) [1 + z], size: O(n^1) [z]
28.71/10.27	  plus: runtime: ?, size: O(n^1) [z + z']
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(27) IntTrsBoundProof (UPPER BOUND(ID))
28.71/10.27	
28.71/10.27	Computed RUNTIME bound using CoFloCo for: plus
28.71/10.27	after applying outer abstraction to obtain an ITS,
28.71/10.27	resulting in: O(n^1) with polynomial bound: 1 + z
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(28)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 }-> 1 + plus(z - 1, z') :|: z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, z'), s'), z') :|: s' >= 0, s' <= z', z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 4 }-> plus(plus(times(z - 2, 0), s2), 0) :|: s2 >= 0, s2 <= 0, z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 4 + 2*z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), s3), 1 + s4) :|: s3 >= 0, s3 <= 1 + (z' - 1), s4 >= 0, s4 <= z' - 1, z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(0, z') :|: z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(0, 0) :|: z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(0, 1 + s'') :|: s'' >= 0, s'' <= z' - 1, z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: {times}
28.71/10.27	Previous analysis results are:
28.71/10.27	  minus: runtime: O(n^1) [1 + z], size: O(n^1) [z]
28.71/10.27	  plus: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(29) ResultPropagationProof (UPPER BOUND(ID))
28.71/10.27	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(30)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 + z }-> 1 + s5 :|: s5 >= 0, s5 <= z - 1 + z', z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + z', z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 4 }-> s7 :|: s7 >= 0, s7 <= 0 + 0, z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 4 + z' }-> s8 :|: s8 >= 0, s8 <= 0 + (1 + s''), s'' >= 0, s'' <= z' - 1, z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, z'), s'), z') :|: s' >= 0, s' <= z', z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 4 }-> plus(plus(times(z - 2, 0), s2), 0) :|: s2 >= 0, s2 <= 0, z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 4 + 2*z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), s3), 1 + s4) :|: s3 >= 0, s3 <= 1 + (z' - 1), s4 >= 0, s4 <= z' - 1, z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: {times}
28.71/10.27	Previous analysis results are:
28.71/10.27	  minus: runtime: O(n^1) [1 + z], size: O(n^1) [z]
28.71/10.27	  plus: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(31) IntTrsBoundProof (UPPER BOUND(ID))
28.71/10.27	
28.71/10.27	Computed SIZE bound using CoFloCo for: times
28.71/10.27	after applying outer abstraction to obtain an ITS,
28.71/10.27	resulting in: O(n^2) with polynomial bound: 2*z*z' + 3*z'
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(32)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 + z }-> 1 + s5 :|: s5 >= 0, s5 <= z - 1 + z', z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + z', z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 4 }-> s7 :|: s7 >= 0, s7 <= 0 + 0, z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 4 + z' }-> s8 :|: s8 >= 0, s8 <= 0 + (1 + s''), s'' >= 0, s'' <= z' - 1, z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, z'), s'), z') :|: s' >= 0, s' <= z', z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 4 }-> plus(plus(times(z - 2, 0), s2), 0) :|: s2 >= 0, s2 <= 0, z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 4 + 2*z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), s3), 1 + s4) :|: s3 >= 0, s3 <= 1 + (z' - 1), s4 >= 0, s4 <= z' - 1, z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: {times}
28.71/10.27	Previous analysis results are:
28.71/10.27	  minus: runtime: O(n^1) [1 + z], size: O(n^1) [z]
28.71/10.27	  plus: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
28.71/10.27	  times: runtime: ?, size: O(n^2) [2*z*z' + 3*z']
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(33) IntTrsBoundProof (UPPER BOUND(ID))
28.71/10.27	
28.71/10.27	Computed RUNTIME bound using KoAT for: times
28.71/10.27	after applying outer abstraction to obtain an ITS,
28.71/10.27	resulting in: O(n^3) with polynomial bound: 12 + 31*z + z*z' + 16*z^2*z' + z'
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(34)
28.71/10.27	Obligation:
28.71/10.27	Complexity RNTS consisting of the following rules:
28.71/10.27	
28.71/10.27	   minus(z) -{ 1 }-> 0 :|: z = 0
28.71/10.27	   minus(z) -{ 1 + z }-> 1 + s :|: s >= 0, s <= z - 1, z - 1 >= 0
28.71/10.27	   plus(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0
28.71/10.27	   plus(z, z') -{ 1 + z }-> 1 + s5 :|: s5 >= 0, s5 <= z - 1 + z', z - 1 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 3 }-> s6 :|: s6 >= 0, s6 <= 0 + z', z = 1 + 0, z' >= 0
28.71/10.27	   times(z, z') -{ 4 }-> s7 :|: s7 >= 0, s7 <= 0 + 0, z = 1 + 0, z' = 0
28.71/10.27	   times(z, z') -{ 4 + z' }-> s8 :|: s8 >= 0, s8 <= 0 + (1 + s''), s'' >= 0, s'' <= z' - 1, z = 1 + 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, z'), s'), z') :|: s' >= 0, s' <= z', z' >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 2 }-> plus(plus(times(z - 2, z'), z'), z') :|: z - 2 >= 0, z' >= 0
28.71/10.27	   times(z, z') -{ 4 }-> plus(plus(times(z - 2, 0), s2), 0) :|: s2 >= 0, s2 <= 0, z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 3 }-> plus(plus(times(z - 2, 0), 0), 0) :|: z - 2 >= 0, z' = 0
28.71/10.27	   times(z, z') -{ 4 + 2*z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), s3), 1 + s4) :|: s3 >= 0, s3 <= 1 + (z' - 1), s4 >= 0, s4 <= z' - 1, z' - 1 >= 0, z - 2 >= 0
28.71/10.27	   times(z, z') -{ 3 + z' }-> plus(plus(times(z - 2, 1 + (z' - 1)), 1 + (z' - 1)), 1 + s1) :|: s1 >= 0, s1 <= z' - 1, z - 2 >= 0, z' - 1 >= 0
28.71/10.27	   times(z, z') -{ 1 }-> 0 :|: z' >= 0, z = 0
28.71/10.27	
28.71/10.27	Function symbols to be analyzed: 
28.71/10.27	Previous analysis results are:
28.71/10.27	  minus: runtime: O(n^1) [1 + z], size: O(n^1) [z]
28.71/10.27	  plus: runtime: O(n^1) [1 + z], size: O(n^1) [z + z']
28.71/10.27	  times: runtime: O(n^3) [12 + 31*z + z*z' + 16*z^2*z' + z'], size: O(n^2) [2*z*z' + 3*z']
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(35) FinalProof (FINISHED)
28.71/10.27	Computed overall runtime complexity
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(36)
28.71/10.27	BOUNDS(1, n^3)
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(37) RenamingProof (BOTH BOUNDS(ID, ID))
28.71/10.27	Renamed function symbols to avoid clashes with predefined symbol.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(38)
28.71/10.27	Obligation:
28.71/10.27	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^3, INF).
28.71/10.27	
28.71/10.27	
28.71/10.27	The TRS R consists of the following rules:
28.71/10.27	
28.71/10.27	   +'(0', y) -> y
28.71/10.27	   +'(s(x), y) -> s(+'(x, y))
28.71/10.27	   +'(p(x), y) -> p(+'(x, y))
28.71/10.27	   minus(0') -> 0'
28.71/10.27	   minus(s(x)) -> p(minus(x))
28.71/10.27	   minus(p(x)) -> s(minus(x))
28.71/10.27	   *'(0', y) -> 0'
28.71/10.27	   *'(s(x), y) -> +'(*'(x, y), y)
28.71/10.27	   *'(p(x), y) -> +'(*'(x, y), minus(y))
28.71/10.27	
28.71/10.27	S is empty.
28.71/10.27	Rewrite Strategy: INNERMOST
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(39) TypeInferenceProof (BOTH BOUNDS(ID, ID))
28.71/10.27	Infered types.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(40)
28.71/10.27	Obligation:
28.71/10.27	Innermost TRS:
28.71/10.27	Rules:
28.71/10.27	+'(0', y) -> y
28.71/10.27	+'(s(x), y) -> s(+'(x, y))
28.71/10.27	+'(p(x), y) -> p(+'(x, y))
28.71/10.27	minus(0') -> 0'
28.71/10.27	minus(s(x)) -> p(minus(x))
28.71/10.27	minus(p(x)) -> s(minus(x))
28.71/10.27	*'(0', y) -> 0'
28.71/10.27	*'(s(x), y) -> +'(*'(x, y), y)
28.71/10.27	*'(p(x), y) -> +'(*'(x, y), minus(y))
28.71/10.27	
28.71/10.27	Types:
28.71/10.27	+' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	0' :: 0':s:p
28.71/10.27	s :: 0':s:p -> 0':s:p
28.71/10.27	p :: 0':s:p -> 0':s:p
28.71/10.27	minus :: 0':s:p -> 0':s:p
28.71/10.27	*' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	hole_0':s:p1_0 :: 0':s:p
28.71/10.27	gen_0':s:p2_0 :: Nat -> 0':s:p
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(41) OrderProof (LOWER BOUND(ID))
28.71/10.27	Heuristically decided to analyse the following defined symbols:
28.71/10.27	+', minus, *'
28.71/10.27	
28.71/10.27	They will be analysed ascendingly in the following order:
28.71/10.27	+' < *'
28.71/10.27	minus < *'
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(42)
28.71/10.27	Obligation:
28.71/10.27	Innermost TRS:
28.71/10.27	Rules:
28.71/10.27	+'(0', y) -> y
28.71/10.27	+'(s(x), y) -> s(+'(x, y))
28.71/10.27	+'(p(x), y) -> p(+'(x, y))
28.71/10.27	minus(0') -> 0'
28.71/10.27	minus(s(x)) -> p(minus(x))
28.71/10.27	minus(p(x)) -> s(minus(x))
28.71/10.27	*'(0', y) -> 0'
28.71/10.27	*'(s(x), y) -> +'(*'(x, y), y)
28.71/10.27	*'(p(x), y) -> +'(*'(x, y), minus(y))
28.71/10.27	
28.71/10.27	Types:
28.71/10.27	+' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	0' :: 0':s:p
28.71/10.27	s :: 0':s:p -> 0':s:p
28.71/10.27	p :: 0':s:p -> 0':s:p
28.71/10.27	minus :: 0':s:p -> 0':s:p
28.71/10.27	*' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	hole_0':s:p1_0 :: 0':s:p
28.71/10.27	gen_0':s:p2_0 :: Nat -> 0':s:p
28.71/10.27	
28.71/10.27	
28.71/10.27	Generator Equations:
28.71/10.27	gen_0':s:p2_0(0) <=> 0'
28.71/10.27	gen_0':s:p2_0(+(x, 1)) <=> s(gen_0':s:p2_0(x))
28.71/10.27	
28.71/10.27	
28.71/10.27	The following defined symbols remain to be analysed:
28.71/10.27	+', minus, *'
28.71/10.27	
28.71/10.27	They will be analysed ascendingly in the following order:
28.71/10.27	+' < *'
28.71/10.27	minus < *'
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(43) RewriteLemmaProof (LOWER BOUND(ID))
28.71/10.27	Proved the following rewrite lemma:
28.71/10.27	+'(gen_0':s:p2_0(n4_0), gen_0':s:p2_0(b)) -> gen_0':s:p2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
28.71/10.27	
28.71/10.27	Induction Base:
28.71/10.27	+'(gen_0':s:p2_0(0), gen_0':s:p2_0(b)) ->_R^Omega(1)
28.71/10.27	gen_0':s:p2_0(b)
28.71/10.27	
28.71/10.27	Induction Step:
28.71/10.27	+'(gen_0':s:p2_0(+(n4_0, 1)), gen_0':s:p2_0(b)) ->_R^Omega(1)
28.71/10.27	s(+'(gen_0':s:p2_0(n4_0), gen_0':s:p2_0(b))) ->_IH
28.71/10.27	s(gen_0':s:p2_0(+(b, c5_0)))
28.71/10.27	
28.71/10.27	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(44)
28.71/10.27	Complex Obligation (BEST)
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(45)
28.71/10.27	Obligation:
28.71/10.27	Proved the lower bound n^1 for the following obligation:
28.71/10.27	
28.71/10.27	Innermost TRS:
28.71/10.27	Rules:
28.71/10.27	+'(0', y) -> y
28.71/10.27	+'(s(x), y) -> s(+'(x, y))
28.71/10.27	+'(p(x), y) -> p(+'(x, y))
28.71/10.27	minus(0') -> 0'
28.71/10.27	minus(s(x)) -> p(minus(x))
28.71/10.27	minus(p(x)) -> s(minus(x))
28.71/10.27	*'(0', y) -> 0'
28.71/10.27	*'(s(x), y) -> +'(*'(x, y), y)
28.71/10.27	*'(p(x), y) -> +'(*'(x, y), minus(y))
28.71/10.27	
28.71/10.27	Types:
28.71/10.27	+' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	0' :: 0':s:p
28.71/10.27	s :: 0':s:p -> 0':s:p
28.71/10.27	p :: 0':s:p -> 0':s:p
28.71/10.27	minus :: 0':s:p -> 0':s:p
28.71/10.27	*' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	hole_0':s:p1_0 :: 0':s:p
28.71/10.27	gen_0':s:p2_0 :: Nat -> 0':s:p
28.71/10.27	
28.71/10.27	
28.71/10.27	Generator Equations:
28.71/10.27	gen_0':s:p2_0(0) <=> 0'
28.71/10.27	gen_0':s:p2_0(+(x, 1)) <=> s(gen_0':s:p2_0(x))
28.71/10.27	
28.71/10.27	
28.71/10.27	The following defined symbols remain to be analysed:
28.71/10.27	+', minus, *'
28.71/10.27	
28.71/10.27	They will be analysed ascendingly in the following order:
28.71/10.27	+' < *'
28.71/10.27	minus < *'
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(46) LowerBoundPropagationProof (FINISHED)
28.71/10.27	Propagated lower bound.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(47)
28.71/10.27	BOUNDS(n^1, INF)
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(48)
28.71/10.27	Obligation:
28.71/10.27	Innermost TRS:
28.71/10.27	Rules:
28.71/10.27	+'(0', y) -> y
28.71/10.27	+'(s(x), y) -> s(+'(x, y))
28.71/10.27	+'(p(x), y) -> p(+'(x, y))
28.71/10.27	minus(0') -> 0'
28.71/10.27	minus(s(x)) -> p(minus(x))
28.71/10.27	minus(p(x)) -> s(minus(x))
28.71/10.27	*'(0', y) -> 0'
28.71/10.27	*'(s(x), y) -> +'(*'(x, y), y)
28.71/10.27	*'(p(x), y) -> +'(*'(x, y), minus(y))
28.71/10.27	
28.71/10.27	Types:
28.71/10.27	+' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	0' :: 0':s:p
28.71/10.27	s :: 0':s:p -> 0':s:p
28.71/10.27	p :: 0':s:p -> 0':s:p
28.71/10.27	minus :: 0':s:p -> 0':s:p
28.71/10.27	*' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	hole_0':s:p1_0 :: 0':s:p
28.71/10.27	gen_0':s:p2_0 :: Nat -> 0':s:p
28.71/10.27	
28.71/10.27	
28.71/10.27	Lemmas:
28.71/10.27	+'(gen_0':s:p2_0(n4_0), gen_0':s:p2_0(b)) -> gen_0':s:p2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
28.71/10.27	
28.71/10.27	
28.71/10.27	Generator Equations:
28.71/10.27	gen_0':s:p2_0(0) <=> 0'
28.71/10.27	gen_0':s:p2_0(+(x, 1)) <=> s(gen_0':s:p2_0(x))
28.71/10.27	
28.71/10.27	
28.71/10.27	The following defined symbols remain to be analysed:
28.71/10.27	minus, *'
28.71/10.27	
28.71/10.27	They will be analysed ascendingly in the following order:
28.71/10.27	minus < *'
28.71/10.27	
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(49) RewriteLemmaProof (LOWER BOUND(ID))
28.71/10.27	Proved the following rewrite lemma:
28.71/10.27	minus(gen_0':s:p2_0(+(1, n667_0))) -> *3_0, rt in Omega(n667_0)
28.71/10.27	
28.71/10.27	Induction Base:
28.71/10.27	minus(gen_0':s:p2_0(+(1, 0)))
28.71/10.27	
28.71/10.27	Induction Step:
28.71/10.27	minus(gen_0':s:p2_0(+(1, +(n667_0, 1)))) ->_R^Omega(1)
28.71/10.27	p(minus(gen_0':s:p2_0(+(1, n667_0)))) ->_IH
28.71/10.27	p(*3_0)
28.71/10.27	
28.71/10.27	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(50)
28.71/10.27	Obligation:
28.71/10.27	Innermost TRS:
28.71/10.27	Rules:
28.71/10.27	+'(0', y) -> y
28.71/10.27	+'(s(x), y) -> s(+'(x, y))
28.71/10.27	+'(p(x), y) -> p(+'(x, y))
28.71/10.27	minus(0') -> 0'
28.71/10.27	minus(s(x)) -> p(minus(x))
28.71/10.27	minus(p(x)) -> s(minus(x))
28.71/10.27	*'(0', y) -> 0'
28.71/10.27	*'(s(x), y) -> +'(*'(x, y), y)
28.71/10.27	*'(p(x), y) -> +'(*'(x, y), minus(y))
28.71/10.27	
28.71/10.27	Types:
28.71/10.27	+' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	0' :: 0':s:p
28.71/10.27	s :: 0':s:p -> 0':s:p
28.71/10.27	p :: 0':s:p -> 0':s:p
28.71/10.27	minus :: 0':s:p -> 0':s:p
28.71/10.27	*' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	hole_0':s:p1_0 :: 0':s:p
28.71/10.27	gen_0':s:p2_0 :: Nat -> 0':s:p
28.71/10.27	
28.71/10.27	
28.71/10.27	Lemmas:
28.71/10.27	+'(gen_0':s:p2_0(n4_0), gen_0':s:p2_0(b)) -> gen_0':s:p2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
28.71/10.27	minus(gen_0':s:p2_0(+(1, n667_0))) -> *3_0, rt in Omega(n667_0)
28.71/10.27	
28.71/10.27	
28.71/10.27	Generator Equations:
28.71/10.27	gen_0':s:p2_0(0) <=> 0'
28.71/10.27	gen_0':s:p2_0(+(x, 1)) <=> s(gen_0':s:p2_0(x))
28.71/10.27	
28.71/10.27	
28.71/10.27	The following defined symbols remain to be analysed:
28.71/10.27	*'
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(51) RewriteLemmaProof (LOWER BOUND(ID))
28.71/10.27	Proved the following rewrite lemma:
28.71/10.27	*'(gen_0':s:p2_0(n1827_0), gen_0':s:p2_0(b)) -> gen_0':s:p2_0(*(n1827_0, b)), rt in Omega(1 + b*n1827_0^2 + n1827_0)
28.71/10.27	
28.71/10.27	Induction Base:
28.71/10.27	*'(gen_0':s:p2_0(0), gen_0':s:p2_0(b)) ->_R^Omega(1)
28.71/10.27	0'
28.71/10.27	
28.71/10.27	Induction Step:
28.71/10.27	*'(gen_0':s:p2_0(+(n1827_0, 1)), gen_0':s:p2_0(b)) ->_R^Omega(1)
28.71/10.27	+'(*'(gen_0':s:p2_0(n1827_0), gen_0':s:p2_0(b)), gen_0':s:p2_0(b)) ->_IH
28.71/10.27	+'(gen_0':s:p2_0(*(c1828_0, b)), gen_0':s:p2_0(b)) ->_L^Omega(1 + b*n1827_0)
28.71/10.27	gen_0':s:p2_0(+(*(n1827_0, b), b))
28.71/10.27	
28.71/10.27	We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3).
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(52)
28.71/10.27	Obligation:
28.71/10.27	Proved the lower bound n^3 for the following obligation:
28.71/10.27	
28.71/10.27	Innermost TRS:
28.71/10.27	Rules:
28.71/10.27	+'(0', y) -> y
28.71/10.27	+'(s(x), y) -> s(+'(x, y))
28.71/10.27	+'(p(x), y) -> p(+'(x, y))
28.71/10.27	minus(0') -> 0'
28.71/10.27	minus(s(x)) -> p(minus(x))
28.71/10.27	minus(p(x)) -> s(minus(x))
28.71/10.27	*'(0', y) -> 0'
28.71/10.27	*'(s(x), y) -> +'(*'(x, y), y)
28.71/10.27	*'(p(x), y) -> +'(*'(x, y), minus(y))
28.71/10.27	
28.71/10.27	Types:
28.71/10.27	+' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	0' :: 0':s:p
28.71/10.27	s :: 0':s:p -> 0':s:p
28.71/10.27	p :: 0':s:p -> 0':s:p
28.71/10.27	minus :: 0':s:p -> 0':s:p
28.71/10.27	*' :: 0':s:p -> 0':s:p -> 0':s:p
28.71/10.27	hole_0':s:p1_0 :: 0':s:p
28.71/10.27	gen_0':s:p2_0 :: Nat -> 0':s:p
28.71/10.27	
28.71/10.27	
28.71/10.27	Lemmas:
28.71/10.27	+'(gen_0':s:p2_0(n4_0), gen_0':s:p2_0(b)) -> gen_0':s:p2_0(+(n4_0, b)), rt in Omega(1 + n4_0)
28.71/10.27	minus(gen_0':s:p2_0(+(1, n667_0))) -> *3_0, rt in Omega(n667_0)
28.71/10.27	
28.71/10.27	
28.71/10.27	Generator Equations:
28.71/10.27	gen_0':s:p2_0(0) <=> 0'
28.71/10.27	gen_0':s:p2_0(+(x, 1)) <=> s(gen_0':s:p2_0(x))
28.71/10.27	
28.71/10.27	
28.71/10.27	The following defined symbols remain to be analysed:
28.71/10.27	*'
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(53) LowerBoundPropagationProof (FINISHED)
28.71/10.27	Propagated lower bound.
28.71/10.27	----------------------------------------
28.71/10.27	
28.71/10.27	(54)
28.71/10.27	BOUNDS(n^3, INF)
28.85/10.72	EOF