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