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