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