369.29/291.54	WORST_CASE(Omega(n^1), O(n^2))
369.38/291.56	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
369.38/291.56	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
369.38/291.56	
369.38/291.56	
369.38/291.56	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
369.38/291.56	
369.38/291.56	(0) CpxTRS
369.38/291.56	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
369.38/291.56	(2) CpxWeightedTrs
369.38/291.56	    (3) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
369.38/291.56	    (4) CpxWeightedTrs
369.38/291.56	    (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
369.38/291.56	    (6) CpxTypedWeightedTrs
369.38/291.56	    (7) CompletionProof [UPPER BOUND(ID), 0 ms]
369.38/291.56	    (8) CpxTypedWeightedCompleteTrs
369.38/291.56	    (9) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
369.38/291.56	    (10) CpxTypedWeightedCompleteTrs
369.38/291.56	    (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms]
369.38/291.56	    (12) CpxRNTS
369.38/291.56	    (13) InliningProof [UPPER BOUND(ID), 473 ms]
369.38/291.56	    (14) CpxRNTS
369.38/291.56	    (15) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
369.38/291.56	    (16) CpxRNTS
369.38/291.56	    (17) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
369.38/291.56	    (18) CpxRNTS
369.38/291.56	    (19) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
369.38/291.56	    (20) CpxRNTS
369.38/291.56	    (21) IntTrsBoundProof [UPPER BOUND(ID), 393 ms]
369.38/291.56	    (22) CpxRNTS
369.38/291.56	    (23) IntTrsBoundProof [UPPER BOUND(ID), 119 ms]
369.38/291.56	    (24) CpxRNTS
369.38/291.56	    (25) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
369.38/291.56	    (26) CpxRNTS
369.38/291.56	    (27) IntTrsBoundProof [UPPER BOUND(ID), 169 ms]
369.38/291.56	    (28) CpxRNTS
369.38/291.56	    (29) IntTrsBoundProof [UPPER BOUND(ID), 42 ms]
369.38/291.56	    (30) CpxRNTS
369.38/291.56	    (31) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
369.38/291.56	    (32) CpxRNTS
369.38/291.56	    (33) IntTrsBoundProof [UPPER BOUND(ID), 1084 ms]
369.38/291.56	    (34) CpxRNTS
369.38/291.56	    (35) IntTrsBoundProof [UPPER BOUND(ID), 1157 ms]
369.38/291.56	    (36) CpxRNTS
369.38/291.56	    (37) FinalProof [FINISHED, 0 ms]
369.38/291.56	    (38) BOUNDS(1, n^2)
369.38/291.56	(39) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms]
369.38/291.56	(40) TRS for Loop Detection
369.38/291.56	    (41) DecreasingLoopProof [LOWER BOUND(ID), 0 ms]
369.38/291.56	    (42) BEST
369.38/291.56	        (43) proven lower bound
369.38/291.56	            (44) LowerBoundPropagationProof [FINISHED, 0 ms]
369.38/291.56	            (45) BOUNDS(n^1, INF)
369.38/291.56	        (46) TRS for Loop Detection
369.38/291.56	
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(0)
369.38/291.56	Obligation:
369.38/291.56	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
369.38/291.56	
369.38/291.56	
369.38/291.56	The TRS R consists of the following rules:
369.38/291.56	
369.38/291.56	   -(x, 0) -> x
369.38/291.56	   -(s(x), s(y)) -> -(x, y)
369.38/291.56	   p(s(x)) -> x
369.38/291.56	   f(s(x), y) -> f(p(-(s(x), y)), p(-(y, s(x))))
369.38/291.56	   f(x, s(y)) -> f(p(-(x, s(y))), p(-(s(y), x)))
369.38/291.56	
369.38/291.56	S is empty.
369.38/291.56	Rewrite Strategy: INNERMOST
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
369.38/291.56	Transformed relative TRS to weighted TRS
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(2)
369.38/291.56	Obligation:
369.38/291.56	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).
369.38/291.56	
369.38/291.56	
369.38/291.56	The TRS R consists of the following rules:
369.38/291.56	
369.38/291.56	   -(x, 0) -> x [1]
369.38/291.56	   -(s(x), s(y)) -> -(x, y) [1]
369.38/291.56	   p(s(x)) -> x [1]
369.38/291.56	   f(s(x), y) -> f(p(-(s(x), y)), p(-(y, s(x)))) [1]
369.38/291.56	   f(x, s(y)) -> f(p(-(x, s(y))), p(-(s(y), x))) [1]
369.38/291.56	
369.38/291.56	Rewrite Strategy: INNERMOST
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(3) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID))
369.38/291.56	Renamed defined symbols to avoid conflicts with arithmetic symbols:
369.38/291.56	
369.38/291.56	- => minus
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(4)
369.38/291.56	Obligation:
369.38/291.56	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2).
369.38/291.56	
369.38/291.56	
369.38/291.56	The TRS R consists of the following rules:
369.38/291.56	
369.38/291.56	   minus(x, 0) -> x [1]
369.38/291.56	   minus(s(x), s(y)) -> minus(x, y) [1]
369.38/291.56	   p(s(x)) -> x [1]
369.38/291.56	   f(s(x), y) -> f(p(minus(s(x), y)), p(minus(y, s(x)))) [1]
369.38/291.56	   f(x, s(y)) -> f(p(minus(x, s(y))), p(minus(s(y), x))) [1]
369.38/291.56	
369.38/291.56	Rewrite Strategy: INNERMOST
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(5) TypeInferenceProof (BOTH BOUNDS(ID, ID))
369.38/291.56	Infered types.
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(6)
369.38/291.56	Obligation:
369.38/291.56	Runtime Complexity Weighted TRS with Types.
369.38/291.56	The TRS R consists of the following rules:
369.38/291.56	
369.38/291.56	   minus(x, 0) -> x [1]
369.38/291.56	   minus(s(x), s(y)) -> minus(x, y) [1]
369.38/291.56	   p(s(x)) -> x [1]
369.38/291.56	   f(s(x), y) -> f(p(minus(s(x), y)), p(minus(y, s(x)))) [1]
369.38/291.56	   f(x, s(y)) -> f(p(minus(x, s(y))), p(minus(s(y), x))) [1]
369.38/291.56	
369.38/291.56	The TRS has the following type information:
369.38/291.56	minus :: 0:s -> 0:s -> 0:s
369.38/291.56	0 :: 0:s
369.38/291.56	s :: 0:s -> 0:s
369.38/291.56	p :: 0:s -> 0:s
369.38/291.56	f :: 0:s -> 0:s -> f
369.38/291.56	
369.38/291.56	Rewrite Strategy: INNERMOST
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(7) CompletionProof (UPPER BOUND(ID))
369.38/291.56	The transformation into a RNTS is sound, since:
369.38/291.56	
369.38/291.56	(a) The obligation is a constructor system where every type has a constant constructor,
369.38/291.56	
369.38/291.56	(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
369.38/291.56	
369.38/291.56	   f_2
369.38/291.56	
369.38/291.56	(c) The following functions are completely defined:
369.38/291.56	
369.38/291.56	   p_1
369.38/291.56	   minus_2
369.38/291.56	
369.38/291.56	Due to the following rules being added:
369.38/291.56	
369.38/291.56	   p(v0) -> 0 [0]
369.38/291.56	   minus(v0, v1) -> 0 [0]
369.38/291.56	
369.38/291.56	And the following fresh constants:    const
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(8)
369.38/291.56	Obligation:
369.38/291.56	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
369.38/291.56	
369.38/291.56	Runtime Complexity Weighted TRS with Types.
369.38/291.56	The TRS R consists of the following rules:
369.38/291.56	
369.38/291.56	   minus(x, 0) -> x [1]
369.38/291.56	   minus(s(x), s(y)) -> minus(x, y) [1]
369.38/291.56	   p(s(x)) -> x [1]
369.38/291.56	   f(s(x), y) -> f(p(minus(s(x), y)), p(minus(y, s(x)))) [1]
369.38/291.56	   f(x, s(y)) -> f(p(minus(x, s(y))), p(minus(s(y), x))) [1]
369.38/291.56	   p(v0) -> 0 [0]
369.38/291.56	   minus(v0, v1) -> 0 [0]
369.38/291.56	
369.38/291.56	The TRS has the following type information:
369.38/291.56	minus :: 0:s -> 0:s -> 0:s
369.38/291.56	0 :: 0:s
369.38/291.56	s :: 0:s -> 0:s
369.38/291.56	p :: 0:s -> 0:s
369.38/291.56	f :: 0:s -> 0:s -> f
369.38/291.56	const :: f
369.38/291.56	
369.38/291.56	Rewrite Strategy: INNERMOST
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(9) NarrowingProof (BOTH BOUNDS(ID, ID))
369.38/291.56	Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(10)
369.38/291.56	Obligation:
369.38/291.56	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
369.38/291.56	
369.38/291.56	Runtime Complexity Weighted TRS with Types.
369.38/291.56	The TRS R consists of the following rules:
369.38/291.56	
369.38/291.56	   minus(x, 0) -> x [1]
369.38/291.56	   minus(s(x), s(y)) -> minus(x, y) [1]
369.38/291.56	   p(s(x)) -> x [1]
369.38/291.56	   f(s(x), 0) -> f(p(s(x)), p(0)) [2]
369.38/291.56	   f(s(x), s(y')) -> f(p(minus(x, y')), p(minus(y', x))) [3]
369.38/291.56	   f(s(x), s(y')) -> f(p(minus(x, y')), p(0)) [2]
369.38/291.56	   f(s(x), s(x')) -> f(p(0), p(minus(x', x))) [2]
369.38/291.56	   f(s(x), y) -> f(p(0), p(0)) [1]
369.38/291.56	   f(s(x''), s(y)) -> f(p(minus(x'', y)), p(minus(y, x''))) [3]
369.38/291.56	   f(s(x''), s(y)) -> f(p(minus(x'', y)), p(0)) [2]
369.38/291.56	   f(0, s(y)) -> f(p(0), p(s(y))) [2]
369.38/291.56	   f(s(y''), s(y)) -> f(p(0), p(minus(y, y''))) [2]
369.38/291.56	   f(x, s(y)) -> f(p(0), p(0)) [1]
369.38/291.56	   p(v0) -> 0 [0]
369.38/291.56	   minus(v0, v1) -> 0 [0]
369.38/291.56	
369.38/291.56	The TRS has the following type information:
369.38/291.56	minus :: 0:s -> 0:s -> 0:s
369.38/291.56	0 :: 0:s
369.38/291.56	s :: 0:s -> 0:s
369.38/291.56	p :: 0:s -> 0:s
369.38/291.56	f :: 0:s -> 0:s -> f
369.38/291.56	const :: f
369.38/291.56	
369.38/291.56	Rewrite Strategy: INNERMOST
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
369.38/291.56	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
369.38/291.56	The constant constructors are abstracted as follows:
369.38/291.56	
369.38/291.56	   0 => 0
369.38/291.56	   const => 0
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(12)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(p(minus(x, y')), p(minus(y', x))) :|: x >= 0, y' >= 0, z = 1 + x, z' = 1 + y'
369.38/291.56	   f(z, z') -{ 2 }-> f(p(minus(x, y')), p(0)) :|: x >= 0, y' >= 0, z = 1 + x, z' = 1 + y'
369.38/291.56	   f(z, z') -{ 3 }-> f(p(minus(x'', y)), p(minus(y, x''))) :|: z = 1 + x'', z' = 1 + y, y >= 0, x'' >= 0
369.38/291.56	   f(z, z') -{ 2 }-> f(p(minus(x'', y)), p(0)) :|: z = 1 + x'', z' = 1 + y, y >= 0, x'' >= 0
369.38/291.56	   f(z, z') -{ 2 }-> f(p(0), p(minus(x', x))) :|: z' = 1 + x', x >= 0, x' >= 0, z = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(p(0), p(minus(y, y''))) :|: z' = 1 + y, z = 1 + y'', y >= 0, y'' >= 0
369.38/291.56	   f(z, z') -{ 1 }-> f(p(0), p(0)) :|: x >= 0, y >= 0, z = 1 + x, z' = y
369.38/291.56	   f(z, z') -{ 1 }-> f(p(0), p(0)) :|: z' = 1 + y, x >= 0, y >= 0, z = x
369.38/291.56	   f(z, z') -{ 2 }-> f(p(0), p(1 + y)) :|: z' = 1 + y, y >= 0, z = 0
369.38/291.56	   f(z, z') -{ 2 }-> f(p(1 + x), p(0)) :|: x >= 0, z = 1 + x, z' = 0
369.38/291.56	   minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0
369.38/291.56	   minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
369.38/291.56	   p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x
369.38/291.56	   p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
369.38/291.56	
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(13) InliningProof (UPPER BOUND(ID))
369.38/291.56	Inlined the following terminating rules on right-hand sides where appropriate:
369.38/291.56	
369.38/291.56	   p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x
369.38/291.56	   p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(14)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: x >= 0, z = 1 + x, z' = 0, x' >= 0, 1 + x = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(p(minus(x, y')), p(minus(y', x))) :|: x >= 0, y' >= 0, z = 1 + x, z' = 1 + y'
369.38/291.56	   f(z, z') -{ 2 }-> f(p(minus(x, y')), 0) :|: x >= 0, y' >= 0, z = 1 + x, z' = 1 + y', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(p(minus(x'', y)), p(minus(y, x''))) :|: z = 1 + x'', z' = 1 + y, y >= 0, x'' >= 0
369.38/291.56	   f(z, z') -{ 2 }-> f(p(minus(x'', y)), 0) :|: z = 1 + x'', z' = 1 + y, y >= 0, x'' >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' = 1 + y, y >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + y = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(0, p(minus(x', x))) :|: z' = 1 + x', x >= 0, x' >= 0, z = 1 + x, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, p(minus(y, y''))) :|: z' = 1 + y, z = 1 + y'', y >= 0, y'' >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: x >= 0, z = 1 + x, z' = 0, v0 >= 0, 1 + x = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: x >= 0, y >= 0, z = 1 + x, z' = y, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' = 1 + y, y >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + y = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z' = 1 + y, x >= 0, y >= 0, z = x, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0
369.38/291.56	   minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
369.38/291.56	   p(z) -{ 1 }-> x :|: x >= 0, z = 1 + x
369.38/291.56	   p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
369.38/291.56	
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(15) SimplificationProof (BOTH BOUNDS(ID, ID))
369.38/291.56	Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(16)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(p(minus(z - 1, z' - 1)), p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 2 }-> f(p(minus(z - 1, z' - 1)), 0) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(0, p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(17) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
369.38/291.56	Found the following analysis order by SCC decomposition:
369.38/291.56	
369.38/291.56	   { minus }
369.38/291.56	   { p }
369.38/291.56	   { f }
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(18)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(p(minus(z - 1, z' - 1)), p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 2 }-> f(p(minus(z - 1, z' - 1)), 0) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(0, p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: {minus}, {p}, {f}
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(19) ResultPropagationProof (UPPER BOUND(ID))
369.38/291.56	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(20)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(p(minus(z - 1, z' - 1)), p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 2 }-> f(p(minus(z - 1, z' - 1)), 0) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(0, p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: {minus}, {p}, {f}
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(21) IntTrsBoundProof (UPPER BOUND(ID))
369.38/291.56	
369.38/291.56	Computed SIZE bound using KoAT for: minus
369.38/291.56	after applying outer abstraction to obtain an ITS,
369.38/291.56	resulting in: O(n^1) with polynomial bound: z
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(22)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(p(minus(z - 1, z' - 1)), p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 2 }-> f(p(minus(z - 1, z' - 1)), 0) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(0, p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: {minus}, {p}, {f}
369.38/291.56	Previous analysis results are:
369.38/291.56	  minus: runtime: ?, size: O(n^1) [z]
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(23) IntTrsBoundProof (UPPER BOUND(ID))
369.38/291.56	
369.38/291.56	Computed RUNTIME bound using CoFloCo for: minus
369.38/291.56	after applying outer abstraction to obtain an ITS,
369.38/291.56	resulting in: O(n^1) with polynomial bound: 1 + z'
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(24)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(p(minus(z - 1, z' - 1)), p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 2 }-> f(p(minus(z - 1, z' - 1)), 0) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(0, p(minus(z' - 1, z - 1))) :|: z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 1 }-> minus(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: {p}, {f}
369.38/291.56	Previous analysis results are:
369.38/291.56	  minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z]
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(25) ResultPropagationProof (UPPER BOUND(ID))
369.38/291.56	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(26)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 + z + z' }-> f(p(s'), p(s'')) :|: s' >= 0, s' <= z - 1, s'' >= 0, s'' <= z' - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 2 + z' }-> f(p(s1), 0) :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 + z }-> f(0, p(s2)) :|: s2 >= 0, s2 <= z' - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: {p}, {f}
369.38/291.56	Previous analysis results are:
369.38/291.56	  minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z]
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(27) IntTrsBoundProof (UPPER BOUND(ID))
369.38/291.56	
369.38/291.56	Computed SIZE bound using KoAT for: p
369.38/291.56	after applying outer abstraction to obtain an ITS,
369.38/291.56	resulting in: O(n^1) with polynomial bound: z
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(28)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 + z + z' }-> f(p(s'), p(s'')) :|: s' >= 0, s' <= z - 1, s'' >= 0, s'' <= z' - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 2 + z' }-> f(p(s1), 0) :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 + z }-> f(0, p(s2)) :|: s2 >= 0, s2 <= z' - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: {p}, {f}
369.38/291.56	Previous analysis results are:
369.38/291.56	  minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z]
369.38/291.56	  p: runtime: ?, size: O(n^1) [z]
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(29) IntTrsBoundProof (UPPER BOUND(ID))
369.38/291.56	
369.38/291.56	Computed RUNTIME bound using CoFloCo for: p
369.38/291.56	after applying outer abstraction to obtain an ITS,
369.38/291.56	resulting in: O(1) with polynomial bound: 1
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(30)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 + z + z' }-> f(p(s'), p(s'')) :|: s' >= 0, s' <= z - 1, s'' >= 0, s'' <= z' - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 2 + z' }-> f(p(s1), 0) :|: s1 >= 0, s1 <= z - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 + z }-> f(0, p(s2)) :|: s2 >= 0, s2 <= z' - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: {f}
369.38/291.56	Previous analysis results are:
369.38/291.56	  minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z]
369.38/291.56	  p: runtime: O(1) [1], size: O(n^1) [z]
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(31) ResultPropagationProof (UPPER BOUND(ID))
369.38/291.56	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(32)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 5 + z + z' }-> f(s3, s4) :|: s3 >= 0, s3 <= s', s4 >= 0, s4 <= s'', s' >= 0, s' <= z - 1, s'' >= 0, s'' <= z' - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 3 + z' }-> f(s5, 0) :|: s5 >= 0, s5 <= s1, s1 >= 0, s1 <= z - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 + z }-> f(0, s6) :|: s6 >= 0, s6 <= s2, s2 >= 0, s2 <= z' - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: {f}
369.38/291.56	Previous analysis results are:
369.38/291.56	  minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z]
369.38/291.56	  p: runtime: O(1) [1], size: O(n^1) [z]
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(33) IntTrsBoundProof (UPPER BOUND(ID))
369.38/291.56	
369.38/291.56	Computed SIZE bound using CoFloCo for: f
369.38/291.56	after applying outer abstraction to obtain an ITS,
369.38/291.56	resulting in: O(1) with polynomial bound: 0
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(34)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 5 + z + z' }-> f(s3, s4) :|: s3 >= 0, s3 <= s', s4 >= 0, s4 <= s'', s' >= 0, s' <= z - 1, s'' >= 0, s'' <= z' - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 3 + z' }-> f(s5, 0) :|: s5 >= 0, s5 <= s1, s1 >= 0, s1 <= z - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 + z }-> f(0, s6) :|: s6 >= 0, s6 <= s2, s2 >= 0, s2 <= z' - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: {f}
369.38/291.56	Previous analysis results are:
369.38/291.56	  minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z]
369.38/291.56	  p: runtime: O(1) [1], size: O(n^1) [z]
369.38/291.56	  f: runtime: ?, size: O(1) [0]
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(35) IntTrsBoundProof (UPPER BOUND(ID))
369.38/291.56	
369.38/291.56	Computed RUNTIME bound using CoFloCo for: f
369.38/291.56	after applying outer abstraction to obtain an ITS,
369.38/291.56	resulting in: O(n^2) with polynomial bound: 17 + 8*z + z*z' + z^2 + 8*z' + z'^2
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(36)
369.38/291.56	Obligation:
369.38/291.56	Complexity RNTS consisting of the following rules:
369.38/291.56	
369.38/291.56	   f(z, z') -{ 5 + z + z' }-> f(s3, s4) :|: s3 >= 0, s3 <= s', s4 >= 0, s4 <= s'', s' >= 0, s' <= z - 1, s'' >= 0, s'' <= z' - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   f(z, z') -{ 3 + z' }-> f(s5, 0) :|: s5 >= 0, s5 <= s1, s1 >= 0, s1 <= z - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(x', 0) :|: z - 1 >= 0, z' = 0, x' >= 0, 1 + (z - 1) = 1 + x', v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 + z }-> f(0, s6) :|: s6 >= 0, s6 <= s2, s2 >= 0, s2 <= z' - 1, z - 1 >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0
369.38/291.56	   f(z, z') -{ 3 }-> f(0, x) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, x >= 0, 1 + (z' - 1) = 1 + x
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z - 1 >= 0, z' = 0, v0 >= 0, 1 + (z - 1) = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z - 1 >= 0, z' >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   f(z, z') -{ 2 }-> f(0, 0) :|: z' - 1 >= 0, z = 0, v0 >= 0, 0 = v0, v0' >= 0, 1 + (z' - 1) = v0'
369.38/291.56	   f(z, z') -{ 1 }-> f(0, 0) :|: z >= 0, z' - 1 >= 0, v0 >= 0, 0 = v0, v0' >= 0, 0 = v0'
369.38/291.56	   minus(z, z') -{ 1 + z' }-> s :|: s >= 0, s <= z - 1, z - 1 >= 0, z' - 1 >= 0
369.38/291.56	   minus(z, z') -{ 1 }-> z :|: z >= 0, z' = 0
369.38/291.56	   minus(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
369.38/291.56	   p(z) -{ 0 }-> 0 :|: z >= 0
369.38/291.56	   p(z) -{ 1 }-> z - 1 :|: z - 1 >= 0
369.38/291.56	
369.38/291.56	Function symbols to be analyzed: 
369.38/291.56	Previous analysis results are:
369.38/291.56	  minus: runtime: O(n^1) [1 + z'], size: O(n^1) [z]
369.38/291.56	  p: runtime: O(1) [1], size: O(n^1) [z]
369.38/291.56	  f: runtime: O(n^2) [17 + 8*z + z*z' + z^2 + 8*z' + z'^2], size: O(1) [0]
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(37) FinalProof (FINISHED)
369.38/291.56	Computed overall runtime complexity
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(38)
369.38/291.56	BOUNDS(1, n^2)
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(39) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID))
369.38/291.56	Transformed a relative TRS into a decreasing-loop problem.
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(40)
369.38/291.56	Obligation:
369.38/291.56	Analyzing the following TRS for decreasing loops:
369.38/291.56	
369.38/291.56	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
369.38/291.56	
369.38/291.56	
369.38/291.56	The TRS R consists of the following rules:
369.38/291.56	
369.38/291.56	   -(x, 0) -> x
369.38/291.56	   -(s(x), s(y)) -> -(x, y)
369.38/291.56	   p(s(x)) -> x
369.38/291.56	   f(s(x), y) -> f(p(-(s(x), y)), p(-(y, s(x))))
369.38/291.56	   f(x, s(y)) -> f(p(-(x, s(y))), p(-(s(y), x)))
369.38/291.56	
369.38/291.56	S is empty.
369.38/291.56	Rewrite Strategy: INNERMOST
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(41) DecreasingLoopProof (LOWER BOUND(ID))
369.38/291.56	The following loop(s) give(s) rise to the lower bound Omega(n^1):
369.38/291.56	
369.38/291.56	The rewrite sequence
369.38/291.56	
369.38/291.56	-(s(x), s(y)) ->^+ -(x, y)
369.38/291.56	
369.38/291.56	gives rise to a decreasing loop by considering the right hand sides subterm at position [].
369.38/291.56	
369.38/291.56	The pumping substitution is [x / s(x), y / s(y)].
369.38/291.56	
369.38/291.56	The result substitution is [ ].
369.38/291.56	
369.38/291.56	
369.38/291.56	
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(42)
369.38/291.56	Complex Obligation (BEST)
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(43)
369.38/291.56	Obligation:
369.38/291.56	Proved the lower bound n^1 for the following obligation:
369.38/291.56	
369.38/291.56	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
369.38/291.56	
369.38/291.56	
369.38/291.56	The TRS R consists of the following rules:
369.38/291.56	
369.38/291.56	   -(x, 0) -> x
369.38/291.56	   -(s(x), s(y)) -> -(x, y)
369.38/291.56	   p(s(x)) -> x
369.38/291.56	   f(s(x), y) -> f(p(-(s(x), y)), p(-(y, s(x))))
369.38/291.56	   f(x, s(y)) -> f(p(-(x, s(y))), p(-(s(y), x)))
369.38/291.56	
369.38/291.56	S is empty.
369.38/291.56	Rewrite Strategy: INNERMOST
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(44) LowerBoundPropagationProof (FINISHED)
369.38/291.56	Propagated lower bound.
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(45)
369.38/291.56	BOUNDS(n^1, INF)
369.38/291.56	
369.38/291.56	----------------------------------------
369.38/291.56	
369.38/291.56	(46)
369.38/291.56	Obligation:
369.38/291.56	Analyzing the following TRS for decreasing loops:
369.38/291.56	
369.38/291.56	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2).
369.38/291.56	
369.38/291.56	
369.38/291.56	The TRS R consists of the following rules:
369.38/291.56	
369.38/291.56	   -(x, 0) -> x
369.38/291.56	   -(s(x), s(y)) -> -(x, y)
369.38/291.56	   p(s(x)) -> x
369.38/291.56	   f(s(x), y) -> f(p(-(s(x), y)), p(-(y, s(x))))
369.38/291.56	   f(x, s(y)) -> f(p(-(x, s(y))), p(-(s(y), x)))
369.38/291.56	
369.38/291.56	S is empty.
369.38/291.56	Rewrite Strategy: INNERMOST
369.63/291.66	EOF