1110.10/291.55	WORST_CASE(Omega(n^2), O(n^3))
1111.03/291.75	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
1111.03/291.75	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
1111.03/291.75	
1111.03/291.75	
1111.03/291.75	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3).
1111.03/291.75	
1111.03/291.75	(0) CpxTRS
1111.03/291.75	(1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms]
1111.03/291.75	(2) CpxWeightedTrs
1111.03/291.75	    (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1111.03/291.75	    (4) CpxTypedWeightedTrs
1111.03/291.75	    (5) CompletionProof [UPPER BOUND(ID), 0 ms]
1111.03/291.75	    (6) CpxTypedWeightedCompleteTrs
1111.03/291.75	    (7) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms]
1111.03/291.75	    (8) CpxTypedWeightedCompleteTrs
1111.03/291.75	    (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 3 ms]
1111.03/291.75	    (10) CpxRNTS
1111.03/291.75	    (11) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms]
1111.03/291.75	    (12) CpxRNTS
1111.03/291.75	    (13) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms]
1111.03/291.75	    (14) CpxRNTS
1111.03/291.75	    (15) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1111.03/291.75	    (16) CpxRNTS
1111.03/291.75	    (17) IntTrsBoundProof [UPPER BOUND(ID), 342 ms]
1111.03/291.75	    (18) CpxRNTS
1111.03/291.75	    (19) IntTrsBoundProof [UPPER BOUND(ID), 168 ms]
1111.03/291.75	    (20) CpxRNTS
1111.03/291.75	    (21) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1111.03/291.75	    (22) CpxRNTS
1111.03/291.75	    (23) IntTrsBoundProof [UPPER BOUND(ID), 383 ms]
1111.03/291.75	    (24) CpxRNTS
1111.03/291.75	    (25) IntTrsBoundProof [UPPER BOUND(ID), 137 ms]
1111.03/291.75	    (26) CpxRNTS
1111.03/291.75	    (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1111.03/291.75	    (28) CpxRNTS
1111.03/291.75	    (29) IntTrsBoundProof [UPPER BOUND(ID), 1155 ms]
1111.03/291.75	    (30) CpxRNTS
1111.03/291.75	    (31) IntTrsBoundProof [UPPER BOUND(ID), 374 ms]
1111.03/291.75	    (32) CpxRNTS
1111.03/291.75	    (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1111.03/291.75	    (34) CpxRNTS
1111.03/291.75	    (35) IntTrsBoundProof [UPPER BOUND(ID), 1888 ms]
1111.03/291.75	    (36) CpxRNTS
1111.03/291.75	    (37) IntTrsBoundProof [UPPER BOUND(ID), 622 ms]
1111.03/291.75	    (38) CpxRNTS
1111.03/291.75	    (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms]
1111.03/291.75	    (40) CpxRNTS
1111.03/291.75	    (41) IntTrsBoundProof [UPPER BOUND(ID), 784 ms]
1111.03/291.75	    (42) CpxRNTS
1111.03/291.75	    (43) IntTrsBoundProof [UPPER BOUND(ID), 165 ms]
1111.03/291.75	    (44) CpxRNTS
1111.03/291.75	    (45) FinalProof [FINISHED, 0 ms]
1111.03/291.75	    (46) BOUNDS(1, n^3)
1111.03/291.75	(47) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms]
1111.03/291.75	(48) CpxTRS
1111.03/291.75	    (49) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms]
1111.03/291.75	    (50) typed CpxTrs
1111.03/291.75	    (51) OrderProof [LOWER BOUND(ID), 4 ms]
1111.03/291.75	    (52) typed CpxTrs
1111.03/291.75	    (53) RewriteLemmaProof [LOWER BOUND(ID), 272 ms]
1111.03/291.75	    (54) BEST
1111.03/291.75	        (55) proven lower bound
1111.03/291.75	            (56) LowerBoundPropagationProof [FINISHED, 0 ms]
1111.03/291.75	            (57) BOUNDS(n^1, INF)
1111.03/291.75	        (58) typed CpxTrs
1111.03/291.75	            (59) RewriteLemmaProof [LOWER BOUND(ID), 52 ms]
1111.03/291.75	            (60) typed CpxTrs
1111.03/291.75	            (61) RewriteLemmaProof [LOWER BOUND(ID), 39 ms]
1111.03/291.75	            (62) typed CpxTrs
1111.03/291.75	            (63) RewriteLemmaProof [LOWER BOUND(ID), 976 ms]
1111.03/291.75	            (64) proven lower bound
1111.03/291.75	            (65) LowerBoundPropagationProof [FINISHED, 0 ms]
1111.03/291.75	            (66) BOUNDS(n^2, INF)
1111.03/291.75	
1111.03/291.75	
1111.03/291.75	----------------------------------------
1111.03/291.75	
1111.03/291.75	(0)
1111.03/291.75	Obligation:
1111.03/291.75	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^3).
1111.03/291.75	
1111.03/291.75	
1111.03/291.75	The TRS R consists of the following rules:
1111.03/291.75	
1111.03/291.75	   eq(0, 0) -> true
1111.03/291.75	   eq(0, s(m)) -> false
1111.03/291.75	   eq(s(n), 0) -> false
1111.03/291.75	   eq(s(n), s(m)) -> eq(n, m)
1111.03/291.75	   le(0, m) -> true
1111.03/291.75	   le(s(n), 0) -> false
1111.03/291.75	   le(s(n), s(m)) -> le(n, m)
1111.03/291.75	   min(cons(0, nil)) -> 0
1111.03/291.75	   min(cons(s(n), nil)) -> s(n)
1111.03/291.75	   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
1111.03/291.75	   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
1111.03/291.75	   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
1111.03/291.75	   replace(n, m, nil) -> nil
1111.03/291.75	   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
1111.03/291.75	   if_replace(true, n, m, cons(k, x)) -> cons(m, x)
1111.03/291.75	   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
1111.03/291.75	   sort(nil) -> nil
1111.03/291.75	   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))
1111.03/291.75	
1111.03/291.75	S is empty.
1111.03/291.75	Rewrite Strategy: INNERMOST
1111.03/291.75	----------------------------------------
1111.03/291.75	
1111.03/291.75	(1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID))
1111.03/291.75	Transformed relative TRS to weighted TRS
1111.03/291.75	----------------------------------------
1111.03/291.75	
1111.03/291.75	(2)
1111.03/291.75	Obligation:
1111.03/291.75	The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^3).
1111.03/291.75	
1111.03/291.75	
1111.03/291.75	The TRS R consists of the following rules:
1111.03/291.75	
1111.03/291.75	   eq(0, 0) -> true [1]
1111.03/291.75	   eq(0, s(m)) -> false [1]
1111.03/291.75	   eq(s(n), 0) -> false [1]
1111.03/291.75	   eq(s(n), s(m)) -> eq(n, m) [1]
1111.03/291.75	   le(0, m) -> true [1]
1111.03/291.75	   le(s(n), 0) -> false [1]
1111.03/291.75	   le(s(n), s(m)) -> le(n, m) [1]
1111.03/291.75	   min(cons(0, nil)) -> 0 [1]
1111.03/291.75	   min(cons(s(n), nil)) -> s(n) [1]
1111.03/291.75	   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) [1]
1111.03/291.75	   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) [1]
1111.03/291.75	   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) [1]
1111.03/291.75	   replace(n, m, nil) -> nil [1]
1111.03/291.75	   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) [1]
1111.03/291.75	   if_replace(true, n, m, cons(k, x)) -> cons(m, x) [1]
1111.03/291.75	   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) [1]
1111.03/291.75	   sort(nil) -> nil [1]
1111.03/291.75	   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) [1]
1111.03/291.75	
1111.03/291.75	Rewrite Strategy: INNERMOST
1111.03/291.75	----------------------------------------
1111.03/291.75	
1111.03/291.75	(3) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1111.03/291.75	Infered types.
1111.03/291.75	----------------------------------------
1111.03/291.75	
1111.03/291.75	(4)
1111.03/291.75	Obligation:
1111.03/291.75	Runtime Complexity Weighted TRS with Types.
1111.03/291.75	The TRS R consists of the following rules:
1111.03/291.75	
1111.03/291.75	   eq(0, 0) -> true [1]
1111.03/291.75	   eq(0, s(m)) -> false [1]
1111.03/291.75	   eq(s(n), 0) -> false [1]
1111.03/291.75	   eq(s(n), s(m)) -> eq(n, m) [1]
1111.03/291.75	   le(0, m) -> true [1]
1111.03/291.75	   le(s(n), 0) -> false [1]
1111.03/291.75	   le(s(n), s(m)) -> le(n, m) [1]
1111.03/291.75	   min(cons(0, nil)) -> 0 [1]
1111.03/291.75	   min(cons(s(n), nil)) -> s(n) [1]
1111.03/291.75	   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) [1]
1111.03/291.75	   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) [1]
1111.03/291.75	   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) [1]
1111.03/291.75	   replace(n, m, nil) -> nil [1]
1111.03/291.75	   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) [1]
1111.03/291.75	   if_replace(true, n, m, cons(k, x)) -> cons(m, x) [1]
1111.03/291.75	   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) [1]
1111.03/291.75	   sort(nil) -> nil [1]
1111.03/291.75	   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) [1]
1111.03/291.75	
1111.03/291.75	The TRS has the following type information:
1111.03/291.75	eq :: 0:s -> 0:s -> true:false
1111.03/291.75	0 :: 0:s
1111.03/291.75	true :: true:false
1111.03/291.75	s :: 0:s -> 0:s
1111.03/291.75	false :: true:false
1111.03/291.75	le :: 0:s -> 0:s -> true:false
1111.03/291.75	min :: nil:cons -> 0:s
1111.03/291.75	cons :: 0:s -> nil:cons -> nil:cons
1111.03/291.75	nil :: nil:cons
1111.03/291.75	if_min :: true:false -> nil:cons -> 0:s
1111.03/291.75	replace :: 0:s -> 0:s -> nil:cons -> nil:cons
1111.03/291.75	if_replace :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons
1111.03/291.75	sort :: nil:cons -> nil:cons
1111.03/291.75	
1111.03/291.75	Rewrite Strategy: INNERMOST
1111.03/291.75	----------------------------------------
1111.03/291.75	
1111.03/291.75	(5) CompletionProof (UPPER BOUND(ID))
1111.03/291.75	The transformation into a RNTS is sound, since:
1111.03/291.75	
1111.03/291.75	(a) The obligation is a constructor system where every type has a constant constructor,
1111.03/291.75	
1111.03/291.75	(b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols:
1111.03/291.75	
1111.03/291.75	   sort_1
1111.03/291.75	
1111.03/291.75	(c) The following functions are completely defined:
1111.03/291.75	
1111.03/291.75	   replace_3
1111.03/291.75	   min_1
1111.03/291.75	   eq_2
1111.03/291.75	   le_2
1111.03/291.75	   if_replace_4
1111.03/291.75	   if_min_2
1111.03/291.75	
1111.03/291.75	Due to the following rules being added:
1111.03/291.75	
1111.03/291.75	   min(v0) -> 0 [0]
1111.03/291.75	   if_replace(v0, v1, v2, v3) -> nil [0]
1111.03/291.75	   if_min(v0, v1) -> 0 [0]
1111.03/291.75	
1111.03/291.75	And the following fresh constants: none
1111.03/291.75	
1111.03/291.75	----------------------------------------
1111.03/291.75	
1111.03/291.75	(6)
1111.03/291.75	Obligation:
1111.03/291.75	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
1111.03/291.75	
1111.03/291.75	Runtime Complexity Weighted TRS with Types.
1111.03/291.75	The TRS R consists of the following rules:
1111.03/291.75	
1111.03/291.75	   eq(0, 0) -> true [1]
1111.03/291.75	   eq(0, s(m)) -> false [1]
1111.03/291.75	   eq(s(n), 0) -> false [1]
1111.03/291.75	   eq(s(n), s(m)) -> eq(n, m) [1]
1111.03/291.75	   le(0, m) -> true [1]
1111.03/291.75	   le(s(n), 0) -> false [1]
1111.03/291.75	   le(s(n), s(m)) -> le(n, m) [1]
1111.03/291.75	   min(cons(0, nil)) -> 0 [1]
1111.03/291.75	   min(cons(s(n), nil)) -> s(n) [1]
1111.03/291.75	   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x))) [1]
1111.03/291.75	   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) [1]
1111.03/291.75	   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) [1]
1111.03/291.75	   replace(n, m, nil) -> nil [1]
1111.03/291.75	   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x)) [1]
1111.03/291.75	   if_replace(true, n, m, cons(k, x)) -> cons(m, x) [1]
1111.03/291.75	   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) [1]
1111.03/291.75	   sort(nil) -> nil [1]
1111.03/291.75	   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x))) [1]
1111.03/291.75	   min(v0) -> 0 [0]
1111.03/291.75	   if_replace(v0, v1, v2, v3) -> nil [0]
1111.03/291.75	   if_min(v0, v1) -> 0 [0]
1111.03/291.76	
1111.03/291.76	The TRS has the following type information:
1111.03/291.76	eq :: 0:s -> 0:s -> true:false
1111.03/291.76	0 :: 0:s
1111.03/291.76	true :: true:false
1111.03/291.76	s :: 0:s -> 0:s
1111.03/291.76	false :: true:false
1111.03/291.76	le :: 0:s -> 0:s -> true:false
1111.03/291.76	min :: nil:cons -> 0:s
1111.03/291.76	cons :: 0:s -> nil:cons -> nil:cons
1111.03/291.76	nil :: nil:cons
1111.03/291.76	if_min :: true:false -> nil:cons -> 0:s
1111.03/291.76	replace :: 0:s -> 0:s -> nil:cons -> nil:cons
1111.03/291.76	if_replace :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons
1111.03/291.76	sort :: nil:cons -> nil:cons
1111.03/291.76	
1111.03/291.76	Rewrite Strategy: INNERMOST
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(7) NarrowingProof (BOTH BOUNDS(ID, ID))
1111.03/291.76	Narrowed the inner basic terms of all right-hand sides by a single narrowing step.
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(8)
1111.03/291.76	Obligation:
1111.03/291.76	Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is:
1111.03/291.76	
1111.03/291.76	Runtime Complexity Weighted TRS with Types.
1111.03/291.76	The TRS R consists of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(0, 0) -> true [1]
1111.03/291.76	   eq(0, s(m)) -> false [1]
1111.03/291.76	   eq(s(n), 0) -> false [1]
1111.03/291.76	   eq(s(n), s(m)) -> eq(n, m) [1]
1111.03/291.76	   le(0, m) -> true [1]
1111.03/291.76	   le(s(n), 0) -> false [1]
1111.03/291.76	   le(s(n), s(m)) -> le(n, m) [1]
1111.03/291.76	   min(cons(0, nil)) -> 0 [1]
1111.03/291.76	   min(cons(s(n), nil)) -> s(n) [1]
1111.03/291.76	   min(cons(0, cons(m, x))) -> if_min(true, cons(0, cons(m, x))) [2]
1111.03/291.76	   min(cons(s(n'), cons(0, x))) -> if_min(false, cons(s(n'), cons(0, x))) [2]
1111.03/291.76	   min(cons(s(n''), cons(s(m'), x))) -> if_min(le(n'', m'), cons(s(n''), cons(s(m'), x))) [2]
1111.03/291.76	   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x)) [1]
1111.03/291.76	   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x)) [1]
1111.03/291.76	   replace(n, m, nil) -> nil [1]
1111.03/291.76	   replace(0, m, cons(0, x)) -> if_replace(true, 0, m, cons(0, x)) [2]
1111.03/291.76	   replace(0, m, cons(s(m''), x)) -> if_replace(false, 0, m, cons(s(m''), x)) [2]
1111.03/291.76	   replace(s(n1), m, cons(0, x)) -> if_replace(false, s(n1), m, cons(0, x)) [2]
1111.03/291.76	   replace(s(n2), m, cons(s(m1), x)) -> if_replace(eq(n2, m1), s(n2), m, cons(s(m1), x)) [2]
1111.03/291.76	   if_replace(true, n, m, cons(k, x)) -> cons(m, x) [1]
1111.03/291.76	   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x)) [1]
1111.03/291.76	   sort(nil) -> nil [1]
1111.03/291.76	   sort(cons(0, nil)) -> cons(min(cons(0, nil)), sort(replace(0, 0, nil))) [2]
1111.03/291.76	   sort(cons(s(n3), nil)) -> cons(min(cons(s(n3), nil)), sort(replace(s(n3), s(n3), nil))) [2]
1111.03/291.76	   sort(cons(n, cons(m2, x'))) -> cons(min(cons(n, cons(m2, x'))), sort(replace(if_min(le(n, m2), cons(n, cons(m2, x'))), n, cons(m2, x')))) [2]
1111.03/291.76	   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(0, n, x))) [1]
1111.03/291.76	   min(v0) -> 0 [0]
1111.03/291.76	   if_replace(v0, v1, v2, v3) -> nil [0]
1111.03/291.76	   if_min(v0, v1) -> 0 [0]
1111.03/291.76	
1111.03/291.76	The TRS has the following type information:
1111.03/291.76	eq :: 0:s -> 0:s -> true:false
1111.03/291.76	0 :: 0:s
1111.03/291.76	true :: true:false
1111.03/291.76	s :: 0:s -> 0:s
1111.03/291.76	false :: true:false
1111.03/291.76	le :: 0:s -> 0:s -> true:false
1111.03/291.76	min :: nil:cons -> 0:s
1111.03/291.76	cons :: 0:s -> nil:cons -> nil:cons
1111.03/291.76	nil :: nil:cons
1111.03/291.76	if_min :: true:false -> nil:cons -> 0:s
1111.03/291.76	replace :: 0:s -> 0:s -> nil:cons -> nil:cons
1111.03/291.76	if_replace :: true:false -> 0:s -> 0:s -> nil:cons -> nil:cons
1111.03/291.76	sort :: nil:cons -> nil:cons
1111.03/291.76	
1111.03/291.76	Rewrite Strategy: INNERMOST
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID))
1111.03/291.76	Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
1111.03/291.76	The constant constructors are abstracted as follows:
1111.03/291.76	
1111.03/291.76	   0 => 0
1111.03/291.76	   true => 1
1111.03/291.76	   false => 0
1111.03/291.76	   nil => 0
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(10)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 1 }-> eq(n, m) :|: n >= 0, z' = 1 + m, z = 1 + n, m >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' = 1 + m, m >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: n >= 0, z = 1 + n, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(n, m, x) :|: n >= 0, x >= 0, z1 = 1 + k + x, z' = n, k >= 0, z = 0, z'' = m, m >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + m + x :|: n >= 0, z = 1, x >= 0, z1 = 1 + k + x, z' = n, k >= 0, z'' = m, m >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> le(n, m) :|: n >= 0, z' = 1 + m, z = 1 + n, m >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z' = m, z = 0, m >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: n >= 0, z = 1 + n, z' = 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0
1111.03/291.76	   min(z) -{ 1 }-> 1 + n :|: z = 1 + (1 + n) + 0, n >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(eq(n2, m1), 1 + n2, m, 1 + (1 + m1) + x) :|: z = 1 + n2, z' = m, z'' = 1 + (1 + m1) + x, x >= 0, n2 >= 0, m1 >= 0, m >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, m, 1 + 0 + x) :|: z' = m, x >= 0, z = 0, z'' = 1 + 0 + x, m >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, m, 1 + (1 + m'') + x) :|: z' = m, m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, m >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + n1, m, 1 + 0 + x) :|: z = 1 + n1, z' = m, x >= 0, n1 >= 0, z'' = 1 + 0 + x, m >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, n >= 0, z = n, z' = m, m >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + n3) + 0) + sort(replace(1 + n3, 1 + n3, 0)) :|: z = 1 + (1 + n3) + 0, n3 >= 0
1111.03/291.76	
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(11) SimplificationProof (BOTH BOUNDS(ID, ID))
1111.03/291.76	Simplified the RNTS by moving equalities from the constraints into the right-hand sides.
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(12)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(13) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID))
1111.03/291.76	Found the following analysis order by SCC decomposition:
1111.03/291.76	
1111.03/291.76	   { le }
1111.03/291.76	   { eq }
1111.03/291.76	   { min, if_min }
1111.03/291.76	   { replace, if_replace }
1111.03/291.76	   { sort }
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(14)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {le}, {eq}, {min,if_min}, {replace,if_replace}, {sort}
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(15) ResultPropagationProof (UPPER BOUND(ID))
1111.03/291.76	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(16)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {le}, {eq}, {min,if_min}, {replace,if_replace}, {sort}
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(17) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.76	
1111.03/291.76	Computed SIZE bound using CoFloCo for: le
1111.03/291.76	after applying outer abstraction to obtain an ITS,
1111.03/291.76	resulting in: O(1) with polynomial bound: 1
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(18)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {le}, {eq}, {min,if_min}, {replace,if_replace}, {sort}
1111.03/291.76	Previous analysis results are:
1111.03/291.76	  le: runtime: ?, size: O(1) [1]
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(19) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.76	
1111.03/291.76	Computed RUNTIME bound using KoAT for: le
1111.03/291.76	after applying outer abstraction to obtain an ITS,
1111.03/291.76	resulting in: O(n^1) with polynomial bound: 2 + z'
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(20)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> le(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(le(n'', m'), 1 + (1 + n'') + (1 + (1 + m') + x)) :|: x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(le(n, m2), 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {eq}, {min,if_min}, {replace,if_replace}, {sort}
1111.03/291.76	Previous analysis results are:
1111.03/291.76	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(21) ResultPropagationProof (UPPER BOUND(ID))
1111.03/291.76	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(22)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {eq}, {min,if_min}, {replace,if_replace}, {sort}
1111.03/291.76	Previous analysis results are:
1111.03/291.76	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(23) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.76	
1111.03/291.76	Computed SIZE bound using CoFloCo for: eq
1111.03/291.76	after applying outer abstraction to obtain an ITS,
1111.03/291.76	resulting in: O(1) with polynomial bound: 1
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(24)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {eq}, {min,if_min}, {replace,if_replace}, {sort}
1111.03/291.76	Previous analysis results are:
1111.03/291.76	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.76	  eq: runtime: ?, size: O(1) [1]
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(25) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.76	
1111.03/291.76	Computed RUNTIME bound using KoAT for: eq
1111.03/291.76	after applying outer abstraction to obtain an ITS,
1111.03/291.76	resulting in: O(n^1) with polynomial bound: 3 + z'
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(26)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 1 }-> eq(z - 1, z' - 1) :|: z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(eq(z - 1, m1), 1 + (z - 1), z', 1 + (1 + m1) + x) :|: z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {min,if_min}, {replace,if_replace}, {sort}
1111.03/291.76	Previous analysis results are:
1111.03/291.76	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.76	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(27) ResultPropagationProof (UPPER BOUND(ID))
1111.03/291.76	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(28)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {min,if_min}, {replace,if_replace}, {sort}
1111.03/291.76	Previous analysis results are:
1111.03/291.76	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.76	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(29) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.76	
1111.03/291.76	Computed SIZE bound using KoAT for: min
1111.03/291.76	after applying outer abstraction to obtain an ITS,
1111.03/291.76	resulting in: O(n^1) with polynomial bound: z
1111.03/291.76	
1111.03/291.76	Computed SIZE bound using KoAT for: if_min
1111.03/291.76	after applying outer abstraction to obtain an ITS,
1111.03/291.76	resulting in: O(n^1) with polynomial bound: z'
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(30)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {min,if_min}, {replace,if_replace}, {sort}
1111.03/291.76	Previous analysis results are:
1111.03/291.76	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.76	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.76	  min: runtime: ?, size: O(n^1) [z]
1111.03/291.76	  if_min: runtime: ?, size: O(n^1) [z']
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(31) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.76	
1111.03/291.76	Computed RUNTIME bound using CoFloCo for: min
1111.03/291.76	after applying outer abstraction to obtain an ITS,
1111.03/291.76	resulting in: O(n^2) with polynomial bound: 5 + 4*z + z^2
1111.03/291.76	
1111.03/291.76	Computed RUNTIME bound using KoAT for: if_min
1111.03/291.76	after applying outer abstraction to obtain an ITS,
1111.03/291.76	resulting in: O(n^2) with polynomial bound: 22 + 24*z' + 8*z'^2
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(32)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + m + x) :|: n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 1 }-> min(1 + n + x) :|: n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 4 + m' }-> if_min(s', 1 + (1 + n'') + (1 + (1 + m') + x)) :|: s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(1, 1 + 0 + (1 + m + x)) :|: x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 2 }-> if_min(0, 1 + (1 + n') + (1 + 0 + x)) :|: x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.76	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.76	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.76	   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.76	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.76	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.76	   sort(z) -{ 1 }-> 1 + min(1 + n + x) + sort(replace(0, n, x)) :|: n >= 0, x >= 0, z = 1 + n + x
1111.03/291.76	   sort(z) -{ 4 + m2 }-> 1 + min(1 + n + (1 + m2 + x')) + sort(replace(if_min(s'', 1 + n + (1 + m2 + x')), n, 1 + m2 + x')) :|: s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + 0 + 0) + sort(replace(0, 0, 0)) :|: z = 1 + 0 + 0
1111.03/291.76	   sort(z) -{ 2 }-> 1 + min(1 + (1 + (z - 2)) + 0) + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: z - 2 >= 0
1111.03/291.76	
1111.03/291.76	Function symbols to be analyzed: {replace,if_replace}, {sort}
1111.03/291.76	Previous analysis results are:
1111.03/291.76	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.76	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.76	  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
1111.03/291.76	  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
1111.03/291.76	
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(33) ResultPropagationProof (UPPER BOUND(ID))
1111.03/291.76	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1111.03/291.76	----------------------------------------
1111.03/291.76	
1111.03/291.76	(34)
1111.03/291.76	Obligation:
1111.03/291.76	Complexity RNTS consisting of the following rules:
1111.03/291.76	
1111.03/291.76	   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.76	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.76	   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.76	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.76	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.76	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.76	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.76	   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.76	   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.76	   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.78	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.78	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.78	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.78	   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.78	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.78	   sort(z) -{ 123 + 65*m2 + 18*m2*n + 18*m2*x' + 9*m2^2 + 64*n + 18*n*x' + 9*n^2 + 64*x' + 9*x'^2 }-> 1 + s10 + sort(replace(s11, n, 1 + m2 + x')) :|: s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.78	   sort(z) -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> 1 + s12 + sort(replace(0, n, x)) :|: s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
1111.03/291.78	   sort(z) -{ 12 }-> 1 + s8 + sort(replace(0, 0, 0)) :|: s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
1111.03/291.78	   sort(z) -{ 7 + 4*z + z^2 }-> 1 + s9 + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0
1111.03/291.78	
1111.03/291.78	Function symbols to be analyzed: {replace,if_replace}, {sort}
1111.03/291.78	Previous analysis results are:
1111.03/291.78	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.78	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.78	  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
1111.03/291.78	  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(35) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.78	
1111.03/291.78	Computed SIZE bound using KoAT for: replace
1111.03/291.78	after applying outer abstraction to obtain an ITS,
1111.03/291.78	resulting in: O(n^1) with polynomial bound: z' + z''
1111.03/291.78	
1111.03/291.78	Computed SIZE bound using CoFloCo for: if_replace
1111.03/291.78	after applying outer abstraction to obtain an ITS,
1111.03/291.78	resulting in: O(n^1) with polynomial bound: z'' + z1
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(36)
1111.03/291.78	Obligation:
1111.03/291.78	Complexity RNTS consisting of the following rules:
1111.03/291.78	
1111.03/291.78	   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.78	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.78	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.78	   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.78	   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.78	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.78	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.78	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.78	   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.78	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.78	   sort(z) -{ 123 + 65*m2 + 18*m2*n + 18*m2*x' + 9*m2^2 + 64*n + 18*n*x' + 9*n^2 + 64*x' + 9*x'^2 }-> 1 + s10 + sort(replace(s11, n, 1 + m2 + x')) :|: s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.78	   sort(z) -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> 1 + s12 + sort(replace(0, n, x)) :|: s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
1111.03/291.78	   sort(z) -{ 12 }-> 1 + s8 + sort(replace(0, 0, 0)) :|: s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
1111.03/291.78	   sort(z) -{ 7 + 4*z + z^2 }-> 1 + s9 + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0
1111.03/291.78	
1111.03/291.78	Function symbols to be analyzed: {replace,if_replace}, {sort}
1111.03/291.78	Previous analysis results are:
1111.03/291.78	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.78	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.78	  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
1111.03/291.78	  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
1111.03/291.78	  replace: runtime: ?, size: O(n^1) [z' + z'']
1111.03/291.78	  if_replace: runtime: ?, size: O(n^1) [z'' + z1]
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(37) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.78	
1111.03/291.78	Computed RUNTIME bound using CoFloCo for: replace
1111.03/291.78	after applying outer abstraction to obtain an ITS,
1111.03/291.78	resulting in: O(n^2) with polynomial bound: 6 + 5*z'' + z''^2
1111.03/291.78	
1111.03/291.78	Computed RUNTIME bound using KoAT for: if_replace
1111.03/291.78	after applying outer abstraction to obtain an ITS,
1111.03/291.78	resulting in: O(n^2) with polynomial bound: 8 + 5*z1 + z1^2
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(38)
1111.03/291.78	Obligation:
1111.03/291.78	Complexity RNTS consisting of the following rules:
1111.03/291.78	
1111.03/291.78	   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.78	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + k + replace(z', z'', x) :|: z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.78	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.78	   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.78	   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.78	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.78	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.78	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.78	   replace(z, z', z'') -{ 5 + m1 }-> if_replace(s2, 1 + (z - 1), z', 1 + (1 + m1) + x) :|: s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 2 }-> if_replace(1, 0, z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 2 }-> if_replace(0, 0, z', 1 + (1 + m'') + x) :|: m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 2 }-> if_replace(0, 1 + (z - 1), z', 1 + 0 + (z'' - 1)) :|: z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.78	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.78	   sort(z) -{ 123 + 65*m2 + 18*m2*n + 18*m2*x' + 9*m2^2 + 64*n + 18*n*x' + 9*n^2 + 64*x' + 9*x'^2 }-> 1 + s10 + sort(replace(s11, n, 1 + m2 + x')) :|: s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.78	   sort(z) -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> 1 + s12 + sort(replace(0, n, x)) :|: s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
1111.03/291.78	   sort(z) -{ 12 }-> 1 + s8 + sort(replace(0, 0, 0)) :|: s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
1111.03/291.78	   sort(z) -{ 7 + 4*z + z^2 }-> 1 + s9 + sort(replace(1 + (z - 2), 1 + (z - 2), 0)) :|: s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0
1111.03/291.78	
1111.03/291.78	Function symbols to be analyzed: {sort}
1111.03/291.78	Previous analysis results are:
1111.03/291.78	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.78	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.78	  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
1111.03/291.78	  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
1111.03/291.78	  replace: runtime: O(n^2) [6 + 5*z'' + z''^2], size: O(n^1) [z' + z'']
1111.03/291.78	  if_replace: runtime: O(n^2) [8 + 5*z1 + z1^2], size: O(n^1) [z'' + z1]
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(39) ResultPropagationProof (UPPER BOUND(ID))
1111.03/291.78	Applied inner abstraction using the recently inferred runtime/size bounds where possible.
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(40)
1111.03/291.78	Obligation:
1111.03/291.78	Complexity RNTS consisting of the following rules:
1111.03/291.78	
1111.03/291.78	   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.78	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 7 + 5*x + x^2 }-> 1 + k + s17 :|: s17 >= 0, s17 <= z'' + x, z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.78	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.78	   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.78	   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.78	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.78	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.78	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.78	   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s13 :|: s13 >= 0, s13 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 24 + 9*m'' + 2*m''*x + m''^2 + 9*x + x^2 }-> s14 :|: s14 >= 0, s14 <= z' + (1 + (1 + m'') + x), m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s15 :|: s15 >= 0, s15 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 27 + 10*m1 + 2*m1*x + m1^2 + 9*x + x^2 }-> s16 :|: s16 >= 0, s16 <= z' + (1 + (1 + m1) + x), s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.78	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.78	   sort(z) -{ 135 + 72*m2 + 18*m2*n + 20*m2*x' + 10*m2^2 + 64*n + 18*n*x' + 9*n^2 + 71*x' + 10*x'^2 }-> 1 + s10 + sort(s20) :|: s20 >= 0, s20 <= n + (1 + m2 + x'), s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.78	   sort(z) -{ 17 + 6*n + 2*n*x + n^2 + 11*x + 2*x^2 }-> 1 + s12 + sort(s21) :|: s21 >= 0, s21 <= n + x, s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
1111.03/291.78	   sort(z) -{ 18 }-> 1 + s8 + sort(s18) :|: s18 >= 0, s18 <= 0 + 0, s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
1111.03/291.78	   sort(z) -{ 13 + 4*z + z^2 }-> 1 + s9 + sort(s19) :|: s19 >= 0, s19 <= 1 + (z - 2) + 0, s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0
1111.03/291.78	
1111.03/291.78	Function symbols to be analyzed: {sort}
1111.03/291.78	Previous analysis results are:
1111.03/291.78	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.78	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.78	  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
1111.03/291.78	  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
1111.03/291.78	  replace: runtime: O(n^2) [6 + 5*z'' + z''^2], size: O(n^1) [z' + z'']
1111.03/291.78	  if_replace: runtime: O(n^2) [8 + 5*z1 + z1^2], size: O(n^1) [z'' + z1]
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(41) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.78	
1111.03/291.78	Computed SIZE bound using CoFloCo for: sort
1111.03/291.78	after applying outer abstraction to obtain an ITS,
1111.03/291.78	resulting in: O(n^2) with polynomial bound: z + z^2
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(42)
1111.03/291.78	Obligation:
1111.03/291.78	Complexity RNTS consisting of the following rules:
1111.03/291.78	
1111.03/291.78	   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.78	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 7 + 5*x + x^2 }-> 1 + k + s17 :|: s17 >= 0, s17 <= z'' + x, z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.78	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.78	   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.78	   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.78	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.78	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.78	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.78	   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s13 :|: s13 >= 0, s13 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 24 + 9*m'' + 2*m''*x + m''^2 + 9*x + x^2 }-> s14 :|: s14 >= 0, s14 <= z' + (1 + (1 + m'') + x), m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s15 :|: s15 >= 0, s15 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 27 + 10*m1 + 2*m1*x + m1^2 + 9*x + x^2 }-> s16 :|: s16 >= 0, s16 <= z' + (1 + (1 + m1) + x), s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.78	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.78	   sort(z) -{ 135 + 72*m2 + 18*m2*n + 20*m2*x' + 10*m2^2 + 64*n + 18*n*x' + 9*n^2 + 71*x' + 10*x'^2 }-> 1 + s10 + sort(s20) :|: s20 >= 0, s20 <= n + (1 + m2 + x'), s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.78	   sort(z) -{ 17 + 6*n + 2*n*x + n^2 + 11*x + 2*x^2 }-> 1 + s12 + sort(s21) :|: s21 >= 0, s21 <= n + x, s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
1111.03/291.78	   sort(z) -{ 18 }-> 1 + s8 + sort(s18) :|: s18 >= 0, s18 <= 0 + 0, s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
1111.03/291.78	   sort(z) -{ 13 + 4*z + z^2 }-> 1 + s9 + sort(s19) :|: s19 >= 0, s19 <= 1 + (z - 2) + 0, s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0
1111.03/291.78	
1111.03/291.78	Function symbols to be analyzed: {sort}
1111.03/291.78	Previous analysis results are:
1111.03/291.78	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.78	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.78	  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
1111.03/291.78	  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
1111.03/291.78	  replace: runtime: O(n^2) [6 + 5*z'' + z''^2], size: O(n^1) [z' + z'']
1111.03/291.78	  if_replace: runtime: O(n^2) [8 + 5*z1 + z1^2], size: O(n^1) [z'' + z1]
1111.03/291.78	  sort: runtime: ?, size: O(n^2) [z + z^2]
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(43) IntTrsBoundProof (UPPER BOUND(ID))
1111.03/291.78	
1111.03/291.78	Computed RUNTIME bound using KoAT for: sort
1111.03/291.78	after applying outer abstraction to obtain an ITS,
1111.03/291.78	resulting in: O(n^3) with polynomial bound: 1 + 183*z + 228*z^2 + 91*z^3
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(44)
1111.03/291.78	Obligation:
1111.03/291.78	Complexity RNTS consisting of the following rules:
1111.03/291.78	
1111.03/291.78	   eq(z, z') -{ 3 + z' }-> s1 :|: s1 >= 0, s1 <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 1 :|: z = 0, z' = 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z = 0, z' - 1 >= 0
1111.03/291.78	   eq(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*n + 2*n*x + n^2 + 6*x + x^2 }-> s6 :|: s6 >= 0, s6 <= 1 + n + x, n >= 0, z = 1, x >= 0, z' = 1 + n + (1 + m + x), m >= 0
1111.03/291.78	   if_min(z, z') -{ 11 + 6*m + 2*m*x + m^2 + 6*x + x^2 }-> s7 :|: s7 >= 0, s7 <= 1 + m + x, n >= 0, x >= 0, z' = 1 + n + (1 + m + x), z = 0, m >= 0
1111.03/291.78	   if_min(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 0 }-> 0 :|: z >= 0, z' >= 0, z'' >= 0, z1 >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 7 + 5*x + x^2 }-> 1 + k + s17 :|: s17 >= 0, s17 <= z'' + x, z' >= 0, x >= 0, z1 = 1 + k + x, k >= 0, z = 0, z'' >= 0
1111.03/291.78	   if_replace(z, z', z'', z1) -{ 1 }-> 1 + z'' + x :|: z' >= 0, z = 1, x >= 0, z1 = 1 + k + x, k >= 0, z'' >= 0
1111.03/291.78	   le(z, z') -{ 2 + z' }-> s :|: s >= 0, s <= 1, z - 1 >= 0, z' - 1 >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 1 :|: z = 0, z' >= 0
1111.03/291.78	   le(z, z') -{ 1 }-> 0 :|: z - 1 >= 0, z' = 0
1111.03/291.78	   min(z) -{ 104 + 56*m + 16*m*x + 8*m^2 + 56*x + 8*x^2 }-> s3 :|: s3 >= 0, s3 <= 1 + 0 + (1 + m + x), x >= 0, z = 1 + 0 + (1 + m + x), m >= 0
1111.03/291.78	   min(z) -{ 168 + 72*n' + 16*n'*x + 8*n'^2 + 72*x + 8*x^2 }-> s4 :|: s4 >= 0, s4 <= 1 + (1 + n') + (1 + 0 + x), x >= 0, z = 1 + (1 + n') + (1 + 0 + x), n' >= 0
1111.03/291.78	   min(z) -{ 250 + 89*m' + 16*m'*n'' + 16*m'*x + 8*m'^2 + 88*n'' + 16*n''*x + 8*n''^2 + 88*x + 8*x^2 }-> s5 :|: s5 >= 0, s5 <= 1 + (1 + n'') + (1 + (1 + m') + x), s' >= 0, s' <= 1, x >= 0, z = 1 + (1 + n'') + (1 + (1 + m') + x), m' >= 0, n'' >= 0
1111.03/291.78	   min(z) -{ 1 }-> 0 :|: z = 1 + 0 + 0
1111.03/291.78	   min(z) -{ 0 }-> 0 :|: z >= 0
1111.03/291.78	   min(z) -{ 1 }-> 1 + (z - 2) :|: z - 2 >= 0
1111.03/291.78	   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s13 :|: s13 >= 0, s13 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 24 + 9*m'' + 2*m''*x + m''^2 + 9*x + x^2 }-> s14 :|: s14 >= 0, s14 <= z' + (1 + (1 + m'') + x), m'' >= 0, x >= 0, z'' = 1 + (1 + m'') + x, z = 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 10 + 5*z'' + z''^2 }-> s15 :|: s15 >= 0, s15 <= z' + (1 + 0 + (z'' - 1)), z'' - 1 >= 0, z - 1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 27 + 10*m1 + 2*m1*x + m1^2 + 9*x + x^2 }-> s16 :|: s16 >= 0, s16 <= z' + (1 + (1 + m1) + x), s2 >= 0, s2 <= 1, z'' = 1 + (1 + m1) + x, x >= 0, z - 1 >= 0, m1 >= 0, z' >= 0
1111.03/291.78	   replace(z, z', z'') -{ 1 }-> 0 :|: z'' = 0, z >= 0, z' >= 0
1111.03/291.78	   sort(z) -{ 1 }-> 0 :|: z = 0
1111.03/291.78	   sort(z) -{ 135 + 72*m2 + 18*m2*n + 20*m2*x' + 10*m2^2 + 64*n + 18*n*x' + 9*n^2 + 71*x' + 10*x'^2 }-> 1 + s10 + sort(s20) :|: s20 >= 0, s20 <= n + (1 + m2 + x'), s10 >= 0, s10 <= 1 + n + (1 + m2 + x'), s11 >= 0, s11 <= 1 + n + (1 + m2 + x'), s'' >= 0, s'' <= 1, n >= 0, x' >= 0, z = 1 + n + (1 + m2 + x'), m2 >= 0
1111.03/291.78	   sort(z) -{ 17 + 6*n + 2*n*x + n^2 + 11*x + 2*x^2 }-> 1 + s12 + sort(s21) :|: s21 >= 0, s21 <= n + x, s12 >= 0, s12 <= 1 + n + x, n >= 0, x >= 0, z = 1 + n + x
1111.03/291.78	   sort(z) -{ 18 }-> 1 + s8 + sort(s18) :|: s18 >= 0, s18 <= 0 + 0, s8 >= 0, s8 <= 1 + 0 + 0, z = 1 + 0 + 0
1111.03/291.78	   sort(z) -{ 13 + 4*z + z^2 }-> 1 + s9 + sort(s19) :|: s19 >= 0, s19 <= 1 + (z - 2) + 0, s9 >= 0, s9 <= 1 + (1 + (z - 2)) + 0, z - 2 >= 0
1111.03/291.78	
1111.03/291.78	Function symbols to be analyzed: 
1111.03/291.78	Previous analysis results are:
1111.03/291.78	  le: runtime: O(n^1) [2 + z'], size: O(1) [1]
1111.03/291.78	  eq: runtime: O(n^1) [3 + z'], size: O(1) [1]
1111.03/291.78	  min: runtime: O(n^2) [5 + 4*z + z^2], size: O(n^1) [z]
1111.03/291.78	  if_min: runtime: O(n^2) [22 + 24*z' + 8*z'^2], size: O(n^1) [z']
1111.03/291.78	  replace: runtime: O(n^2) [6 + 5*z'' + z''^2], size: O(n^1) [z' + z'']
1111.03/291.78	  if_replace: runtime: O(n^2) [8 + 5*z1 + z1^2], size: O(n^1) [z'' + z1]
1111.03/291.78	  sort: runtime: O(n^3) [1 + 183*z + 228*z^2 + 91*z^3], size: O(n^2) [z + z^2]
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(45) FinalProof (FINISHED)
1111.03/291.78	Computed overall runtime complexity
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(46)
1111.03/291.78	BOUNDS(1, n^3)
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(47) RenamingProof (BOTH BOUNDS(ID, ID))
1111.03/291.78	Renamed function symbols to avoid clashes with predefined symbol.
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(48)
1111.03/291.78	Obligation:
1111.03/291.78	The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF).
1111.03/291.78	
1111.03/291.78	
1111.03/291.78	The TRS R consists of the following rules:
1111.03/291.78	
1111.03/291.78	   eq(0', 0') -> true
1111.03/291.78	   eq(0', s(m)) -> false
1111.03/291.78	   eq(s(n), 0') -> false
1111.03/291.78	   eq(s(n), s(m)) -> eq(n, m)
1111.03/291.78	   le(0', m) -> true
1111.03/291.78	   le(s(n), 0') -> false
1111.03/291.78	   le(s(n), s(m)) -> le(n, m)
1111.03/291.78	   min(cons(0', nil)) -> 0'
1111.03/291.78	   min(cons(s(n), nil)) -> s(n)
1111.03/291.78	   min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
1111.03/291.78	   if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
1111.03/291.78	   if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
1111.03/291.78	   replace(n, m, nil) -> nil
1111.03/291.78	   replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
1111.03/291.78	   if_replace(true, n, m, cons(k, x)) -> cons(m, x)
1111.03/291.78	   if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
1111.03/291.78	   sort(nil) -> nil
1111.03/291.78	   sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))
1111.03/291.78	
1111.03/291.78	S is empty.
1111.03/291.78	Rewrite Strategy: INNERMOST
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(49) TypeInferenceProof (BOTH BOUNDS(ID, ID))
1111.03/291.78	Infered types.
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(50)
1111.03/291.78	Obligation:
1111.03/291.78	Innermost TRS:
1111.03/291.78	Rules:
1111.03/291.78	eq(0', 0') -> true
1111.03/291.78	eq(0', s(m)) -> false
1111.03/291.78	eq(s(n), 0') -> false
1111.03/291.78	eq(s(n), s(m)) -> eq(n, m)
1111.03/291.78	le(0', m) -> true
1111.03/291.78	le(s(n), 0') -> false
1111.03/291.78	le(s(n), s(m)) -> le(n, m)
1111.03/291.78	min(cons(0', nil)) -> 0'
1111.03/291.78	min(cons(s(n), nil)) -> s(n)
1111.03/291.78	min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
1111.03/291.78	if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
1111.03/291.78	if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
1111.03/291.78	replace(n, m, nil) -> nil
1111.03/291.78	replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
1111.03/291.78	if_replace(true, n, m, cons(k, x)) -> cons(m, x)
1111.03/291.78	if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
1111.03/291.78	sort(nil) -> nil
1111.03/291.78	sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))
1111.03/291.78	
1111.03/291.78	Types:
1111.03/291.78	eq :: 0':s -> 0':s -> true:false
1111.03/291.78	0' :: 0':s
1111.03/291.78	true :: true:false
1111.03/291.78	s :: 0':s -> 0':s
1111.03/291.78	false :: true:false
1111.03/291.78	le :: 0':s -> 0':s -> true:false
1111.03/291.78	min :: nil:cons -> 0':s
1111.03/291.78	cons :: 0':s -> nil:cons -> nil:cons
1111.03/291.78	nil :: nil:cons
1111.03/291.78	if_min :: true:false -> nil:cons -> 0':s
1111.03/291.78	replace :: 0':s -> 0':s -> nil:cons -> nil:cons
1111.03/291.78	if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
1111.03/291.78	sort :: nil:cons -> nil:cons
1111.03/291.78	hole_true:false1_0 :: true:false
1111.03/291.78	hole_0':s2_0 :: 0':s
1111.03/291.78	hole_nil:cons3_0 :: nil:cons
1111.03/291.78	gen_0':s4_0 :: Nat -> 0':s
1111.03/291.78	gen_nil:cons5_0 :: Nat -> nil:cons
1111.03/291.78	
1111.03/291.78	----------------------------------------
1111.03/291.78	
1111.03/291.78	(51) OrderProof (LOWER BOUND(ID))
1111.22/291.78	Heuristically decided to analyse the following defined symbols:
1111.22/291.78	eq, le, min, replace, sort
1111.22/291.78	
1111.22/291.78	They will be analysed ascendingly in the following order:
1111.22/291.78	eq < replace
1111.22/291.78	le < min
1111.22/291.78	min < sort
1111.22/291.78	replace < sort
1111.22/291.78	
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(52)
1111.22/291.78	Obligation:
1111.22/291.78	Innermost TRS:
1111.22/291.78	Rules:
1111.22/291.78	eq(0', 0') -> true
1111.22/291.78	eq(0', s(m)) -> false
1111.22/291.78	eq(s(n), 0') -> false
1111.22/291.78	eq(s(n), s(m)) -> eq(n, m)
1111.22/291.78	le(0', m) -> true
1111.22/291.78	le(s(n), 0') -> false
1111.22/291.78	le(s(n), s(m)) -> le(n, m)
1111.22/291.78	min(cons(0', nil)) -> 0'
1111.22/291.78	min(cons(s(n), nil)) -> s(n)
1111.22/291.78	min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
1111.22/291.78	if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
1111.22/291.78	if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
1111.22/291.78	replace(n, m, nil) -> nil
1111.22/291.78	replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
1111.22/291.78	if_replace(true, n, m, cons(k, x)) -> cons(m, x)
1111.22/291.78	if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
1111.22/291.78	sort(nil) -> nil
1111.22/291.78	sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))
1111.22/291.78	
1111.22/291.78	Types:
1111.22/291.78	eq :: 0':s -> 0':s -> true:false
1111.22/291.78	0' :: 0':s
1111.22/291.78	true :: true:false
1111.22/291.78	s :: 0':s -> 0':s
1111.22/291.78	false :: true:false
1111.22/291.78	le :: 0':s -> 0':s -> true:false
1111.22/291.78	min :: nil:cons -> 0':s
1111.22/291.78	cons :: 0':s -> nil:cons -> nil:cons
1111.22/291.78	nil :: nil:cons
1111.22/291.78	if_min :: true:false -> nil:cons -> 0':s
1111.22/291.78	replace :: 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	sort :: nil:cons -> nil:cons
1111.22/291.78	hole_true:false1_0 :: true:false
1111.22/291.78	hole_0':s2_0 :: 0':s
1111.22/291.78	hole_nil:cons3_0 :: nil:cons
1111.22/291.78	gen_0':s4_0 :: Nat -> 0':s
1111.22/291.78	gen_nil:cons5_0 :: Nat -> nil:cons
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Generator Equations:
1111.22/291.78	gen_0':s4_0(0) <=> 0'
1111.22/291.78	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1111.22/291.78	gen_nil:cons5_0(0) <=> nil
1111.22/291.78	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	The following defined symbols remain to be analysed:
1111.22/291.78	eq, le, min, replace, sort
1111.22/291.78	
1111.22/291.78	They will be analysed ascendingly in the following order:
1111.22/291.78	eq < replace
1111.22/291.78	le < min
1111.22/291.78	min < sort
1111.22/291.78	replace < sort
1111.22/291.78	
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(53) RewriteLemmaProof (LOWER BOUND(ID))
1111.22/291.78	Proved the following rewrite lemma:
1111.22/291.78	eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
1111.22/291.78	
1111.22/291.78	Induction Base:
1111.22/291.78	eq(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1)
1111.22/291.78	true
1111.22/291.78	
1111.22/291.78	Induction Step:
1111.22/291.78	eq(gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(+(n7_0, 1))) ->_R^Omega(1)
1111.22/291.78	eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) ->_IH
1111.22/291.78	true
1111.22/291.78	
1111.22/291.78	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(54)
1111.22/291.78	Complex Obligation (BEST)
1111.22/291.78	
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(55)
1111.22/291.78	Obligation:
1111.22/291.78	Proved the lower bound n^1 for the following obligation:
1111.22/291.78	
1111.22/291.78	Innermost TRS:
1111.22/291.78	Rules:
1111.22/291.78	eq(0', 0') -> true
1111.22/291.78	eq(0', s(m)) -> false
1111.22/291.78	eq(s(n), 0') -> false
1111.22/291.78	eq(s(n), s(m)) -> eq(n, m)
1111.22/291.78	le(0', m) -> true
1111.22/291.78	le(s(n), 0') -> false
1111.22/291.78	le(s(n), s(m)) -> le(n, m)
1111.22/291.78	min(cons(0', nil)) -> 0'
1111.22/291.78	min(cons(s(n), nil)) -> s(n)
1111.22/291.78	min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
1111.22/291.78	if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
1111.22/291.78	if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
1111.22/291.78	replace(n, m, nil) -> nil
1111.22/291.78	replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
1111.22/291.78	if_replace(true, n, m, cons(k, x)) -> cons(m, x)
1111.22/291.78	if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
1111.22/291.78	sort(nil) -> nil
1111.22/291.78	sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))
1111.22/291.78	
1111.22/291.78	Types:
1111.22/291.78	eq :: 0':s -> 0':s -> true:false
1111.22/291.78	0' :: 0':s
1111.22/291.78	true :: true:false
1111.22/291.78	s :: 0':s -> 0':s
1111.22/291.78	false :: true:false
1111.22/291.78	le :: 0':s -> 0':s -> true:false
1111.22/291.78	min :: nil:cons -> 0':s
1111.22/291.78	cons :: 0':s -> nil:cons -> nil:cons
1111.22/291.78	nil :: nil:cons
1111.22/291.78	if_min :: true:false -> nil:cons -> 0':s
1111.22/291.78	replace :: 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	sort :: nil:cons -> nil:cons
1111.22/291.78	hole_true:false1_0 :: true:false
1111.22/291.78	hole_0':s2_0 :: 0':s
1111.22/291.78	hole_nil:cons3_0 :: nil:cons
1111.22/291.78	gen_0':s4_0 :: Nat -> 0':s
1111.22/291.78	gen_nil:cons5_0 :: Nat -> nil:cons
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Generator Equations:
1111.22/291.78	gen_0':s4_0(0) <=> 0'
1111.22/291.78	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1111.22/291.78	gen_nil:cons5_0(0) <=> nil
1111.22/291.78	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	The following defined symbols remain to be analysed:
1111.22/291.78	eq, le, min, replace, sort
1111.22/291.78	
1111.22/291.78	They will be analysed ascendingly in the following order:
1111.22/291.78	eq < replace
1111.22/291.78	le < min
1111.22/291.78	min < sort
1111.22/291.78	replace < sort
1111.22/291.78	
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(56) LowerBoundPropagationProof (FINISHED)
1111.22/291.78	Propagated lower bound.
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(57)
1111.22/291.78	BOUNDS(n^1, INF)
1111.22/291.78	
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(58)
1111.22/291.78	Obligation:
1111.22/291.78	Innermost TRS:
1111.22/291.78	Rules:
1111.22/291.78	eq(0', 0') -> true
1111.22/291.78	eq(0', s(m)) -> false
1111.22/291.78	eq(s(n), 0') -> false
1111.22/291.78	eq(s(n), s(m)) -> eq(n, m)
1111.22/291.78	le(0', m) -> true
1111.22/291.78	le(s(n), 0') -> false
1111.22/291.78	le(s(n), s(m)) -> le(n, m)
1111.22/291.78	min(cons(0', nil)) -> 0'
1111.22/291.78	min(cons(s(n), nil)) -> s(n)
1111.22/291.78	min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
1111.22/291.78	if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
1111.22/291.78	if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
1111.22/291.78	replace(n, m, nil) -> nil
1111.22/291.78	replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
1111.22/291.78	if_replace(true, n, m, cons(k, x)) -> cons(m, x)
1111.22/291.78	if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
1111.22/291.78	sort(nil) -> nil
1111.22/291.78	sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))
1111.22/291.78	
1111.22/291.78	Types:
1111.22/291.78	eq :: 0':s -> 0':s -> true:false
1111.22/291.78	0' :: 0':s
1111.22/291.78	true :: true:false
1111.22/291.78	s :: 0':s -> 0':s
1111.22/291.78	false :: true:false
1111.22/291.78	le :: 0':s -> 0':s -> true:false
1111.22/291.78	min :: nil:cons -> 0':s
1111.22/291.78	cons :: 0':s -> nil:cons -> nil:cons
1111.22/291.78	nil :: nil:cons
1111.22/291.78	if_min :: true:false -> nil:cons -> 0':s
1111.22/291.78	replace :: 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	sort :: nil:cons -> nil:cons
1111.22/291.78	hole_true:false1_0 :: true:false
1111.22/291.78	hole_0':s2_0 :: 0':s
1111.22/291.78	hole_nil:cons3_0 :: nil:cons
1111.22/291.78	gen_0':s4_0 :: Nat -> 0':s
1111.22/291.78	gen_nil:cons5_0 :: Nat -> nil:cons
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Lemmas:
1111.22/291.78	eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Generator Equations:
1111.22/291.78	gen_0':s4_0(0) <=> 0'
1111.22/291.78	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1111.22/291.78	gen_nil:cons5_0(0) <=> nil
1111.22/291.78	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	The following defined symbols remain to be analysed:
1111.22/291.78	le, min, replace, sort
1111.22/291.78	
1111.22/291.78	They will be analysed ascendingly in the following order:
1111.22/291.78	le < min
1111.22/291.78	min < sort
1111.22/291.78	replace < sort
1111.22/291.78	
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(59) RewriteLemmaProof (LOWER BOUND(ID))
1111.22/291.78	Proved the following rewrite lemma:
1111.22/291.78	le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) -> true, rt in Omega(1 + n548_0)
1111.22/291.78	
1111.22/291.78	Induction Base:
1111.22/291.78	le(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1)
1111.22/291.78	true
1111.22/291.78	
1111.22/291.78	Induction Step:
1111.22/291.78	le(gen_0':s4_0(+(n548_0, 1)), gen_0':s4_0(+(n548_0, 1))) ->_R^Omega(1)
1111.22/291.78	le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) ->_IH
1111.22/291.78	true
1111.22/291.78	
1111.22/291.78	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(60)
1111.22/291.78	Obligation:
1111.22/291.78	Innermost TRS:
1111.22/291.78	Rules:
1111.22/291.78	eq(0', 0') -> true
1111.22/291.78	eq(0', s(m)) -> false
1111.22/291.78	eq(s(n), 0') -> false
1111.22/291.78	eq(s(n), s(m)) -> eq(n, m)
1111.22/291.78	le(0', m) -> true
1111.22/291.78	le(s(n), 0') -> false
1111.22/291.78	le(s(n), s(m)) -> le(n, m)
1111.22/291.78	min(cons(0', nil)) -> 0'
1111.22/291.78	min(cons(s(n), nil)) -> s(n)
1111.22/291.78	min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
1111.22/291.78	if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
1111.22/291.78	if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
1111.22/291.78	replace(n, m, nil) -> nil
1111.22/291.78	replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
1111.22/291.78	if_replace(true, n, m, cons(k, x)) -> cons(m, x)
1111.22/291.78	if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
1111.22/291.78	sort(nil) -> nil
1111.22/291.78	sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))
1111.22/291.78	
1111.22/291.78	Types:
1111.22/291.78	eq :: 0':s -> 0':s -> true:false
1111.22/291.78	0' :: 0':s
1111.22/291.78	true :: true:false
1111.22/291.78	s :: 0':s -> 0':s
1111.22/291.78	false :: true:false
1111.22/291.78	le :: 0':s -> 0':s -> true:false
1111.22/291.78	min :: nil:cons -> 0':s
1111.22/291.78	cons :: 0':s -> nil:cons -> nil:cons
1111.22/291.78	nil :: nil:cons
1111.22/291.78	if_min :: true:false -> nil:cons -> 0':s
1111.22/291.78	replace :: 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	sort :: nil:cons -> nil:cons
1111.22/291.78	hole_true:false1_0 :: true:false
1111.22/291.78	hole_0':s2_0 :: 0':s
1111.22/291.78	hole_nil:cons3_0 :: nil:cons
1111.22/291.78	gen_0':s4_0 :: Nat -> 0':s
1111.22/291.78	gen_nil:cons5_0 :: Nat -> nil:cons
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Lemmas:
1111.22/291.78	eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
1111.22/291.78	le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) -> true, rt in Omega(1 + n548_0)
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Generator Equations:
1111.22/291.78	gen_0':s4_0(0) <=> 0'
1111.22/291.78	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1111.22/291.78	gen_nil:cons5_0(0) <=> nil
1111.22/291.78	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	The following defined symbols remain to be analysed:
1111.22/291.78	min, replace, sort
1111.22/291.78	
1111.22/291.78	They will be analysed ascendingly in the following order:
1111.22/291.78	min < sort
1111.22/291.78	replace < sort
1111.22/291.78	
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(61) RewriteLemmaProof (LOWER BOUND(ID))
1111.22/291.78	Proved the following rewrite lemma:
1111.22/291.78	min(gen_nil:cons5_0(+(1, n883_0))) -> gen_0':s4_0(0), rt in Omega(1 + n883_0)
1111.22/291.78	
1111.22/291.78	Induction Base:
1111.22/291.78	min(gen_nil:cons5_0(+(1, 0))) ->_R^Omega(1)
1111.22/291.78	0'
1111.22/291.78	
1111.22/291.78	Induction Step:
1111.22/291.78	min(gen_nil:cons5_0(+(1, +(n883_0, 1)))) ->_R^Omega(1)
1111.22/291.78	if_min(le(0', 0'), cons(0', cons(0', gen_nil:cons5_0(n883_0)))) ->_L^Omega(1)
1111.22/291.78	if_min(true, cons(0', cons(0', gen_nil:cons5_0(n883_0)))) ->_R^Omega(1)
1111.22/291.78	min(cons(0', gen_nil:cons5_0(n883_0))) ->_IH
1111.22/291.78	gen_0':s4_0(0)
1111.22/291.78	
1111.22/291.78	We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n).
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(62)
1111.22/291.78	Obligation:
1111.22/291.78	Innermost TRS:
1111.22/291.78	Rules:
1111.22/291.78	eq(0', 0') -> true
1111.22/291.78	eq(0', s(m)) -> false
1111.22/291.78	eq(s(n), 0') -> false
1111.22/291.78	eq(s(n), s(m)) -> eq(n, m)
1111.22/291.78	le(0', m) -> true
1111.22/291.78	le(s(n), 0') -> false
1111.22/291.78	le(s(n), s(m)) -> le(n, m)
1111.22/291.78	min(cons(0', nil)) -> 0'
1111.22/291.78	min(cons(s(n), nil)) -> s(n)
1111.22/291.78	min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
1111.22/291.78	if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
1111.22/291.78	if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
1111.22/291.78	replace(n, m, nil) -> nil
1111.22/291.78	replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
1111.22/291.78	if_replace(true, n, m, cons(k, x)) -> cons(m, x)
1111.22/291.78	if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
1111.22/291.78	sort(nil) -> nil
1111.22/291.78	sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))
1111.22/291.78	
1111.22/291.78	Types:
1111.22/291.78	eq :: 0':s -> 0':s -> true:false
1111.22/291.78	0' :: 0':s
1111.22/291.78	true :: true:false
1111.22/291.78	s :: 0':s -> 0':s
1111.22/291.78	false :: true:false
1111.22/291.78	le :: 0':s -> 0':s -> true:false
1111.22/291.78	min :: nil:cons -> 0':s
1111.22/291.78	cons :: 0':s -> nil:cons -> nil:cons
1111.22/291.78	nil :: nil:cons
1111.22/291.78	if_min :: true:false -> nil:cons -> 0':s
1111.22/291.78	replace :: 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	sort :: nil:cons -> nil:cons
1111.22/291.78	hole_true:false1_0 :: true:false
1111.22/291.78	hole_0':s2_0 :: 0':s
1111.22/291.78	hole_nil:cons3_0 :: nil:cons
1111.22/291.78	gen_0':s4_0 :: Nat -> 0':s
1111.22/291.78	gen_nil:cons5_0 :: Nat -> nil:cons
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Lemmas:
1111.22/291.78	eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
1111.22/291.78	le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) -> true, rt in Omega(1 + n548_0)
1111.22/291.78	min(gen_nil:cons5_0(+(1, n883_0))) -> gen_0':s4_0(0), rt in Omega(1 + n883_0)
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Generator Equations:
1111.22/291.78	gen_0':s4_0(0) <=> 0'
1111.22/291.78	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1111.22/291.78	gen_nil:cons5_0(0) <=> nil
1111.22/291.78	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	The following defined symbols remain to be analysed:
1111.22/291.78	replace, sort
1111.22/291.78	
1111.22/291.78	They will be analysed ascendingly in the following order:
1111.22/291.78	replace < sort
1111.22/291.78	
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(63) RewriteLemmaProof (LOWER BOUND(ID))
1111.22/291.78	Proved the following rewrite lemma:
1111.22/291.78	sort(gen_nil:cons5_0(+(1, n1604_0))) -> *6_0, rt in Omega(n1604_0 + n1604_0^2)
1111.22/291.78	
1111.22/291.78	Induction Base:
1111.22/291.78	sort(gen_nil:cons5_0(+(1, 0)))
1111.22/291.78	
1111.22/291.78	Induction Step:
1111.22/291.78	sort(gen_nil:cons5_0(+(1, +(n1604_0, 1)))) ->_R^Omega(1)
1111.22/291.78	cons(min(cons(0', gen_nil:cons5_0(+(1, n1604_0)))), sort(replace(min(cons(0', gen_nil:cons5_0(+(1, n1604_0)))), 0', gen_nil:cons5_0(+(1, n1604_0))))) ->_L^Omega(2 + n1604_0)
1111.22/291.78	cons(gen_0':s4_0(0), sort(replace(min(cons(0', gen_nil:cons5_0(+(1, n1604_0)))), 0', gen_nil:cons5_0(+(1, n1604_0))))) ->_L^Omega(2 + n1604_0)
1111.22/291.78	cons(gen_0':s4_0(0), sort(replace(gen_0':s4_0(0), 0', gen_nil:cons5_0(+(1, n1604_0))))) ->_R^Omega(1)
1111.22/291.78	cons(gen_0':s4_0(0), sort(if_replace(eq(gen_0':s4_0(0), 0'), gen_0':s4_0(0), 0', cons(0', gen_nil:cons5_0(n1604_0))))) ->_L^Omega(1)
1111.22/291.78	cons(gen_0':s4_0(0), sort(if_replace(true, gen_0':s4_0(0), 0', cons(0', gen_nil:cons5_0(n1604_0))))) ->_R^Omega(1)
1111.22/291.78	cons(gen_0':s4_0(0), sort(cons(0', gen_nil:cons5_0(n1604_0)))) ->_IH
1111.22/291.78	cons(gen_0':s4_0(0), *6_0)
1111.22/291.78	
1111.22/291.78	We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2).
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(64)
1111.22/291.78	Obligation:
1111.22/291.78	Proved the lower bound n^2 for the following obligation:
1111.22/291.78	
1111.22/291.78	Innermost TRS:
1111.22/291.78	Rules:
1111.22/291.78	eq(0', 0') -> true
1111.22/291.78	eq(0', s(m)) -> false
1111.22/291.78	eq(s(n), 0') -> false
1111.22/291.78	eq(s(n), s(m)) -> eq(n, m)
1111.22/291.78	le(0', m) -> true
1111.22/291.78	le(s(n), 0') -> false
1111.22/291.78	le(s(n), s(m)) -> le(n, m)
1111.22/291.78	min(cons(0', nil)) -> 0'
1111.22/291.78	min(cons(s(n), nil)) -> s(n)
1111.22/291.78	min(cons(n, cons(m, x))) -> if_min(le(n, m), cons(n, cons(m, x)))
1111.22/291.78	if_min(true, cons(n, cons(m, x))) -> min(cons(n, x))
1111.22/291.78	if_min(false, cons(n, cons(m, x))) -> min(cons(m, x))
1111.22/291.78	replace(n, m, nil) -> nil
1111.22/291.78	replace(n, m, cons(k, x)) -> if_replace(eq(n, k), n, m, cons(k, x))
1111.22/291.78	if_replace(true, n, m, cons(k, x)) -> cons(m, x)
1111.22/291.78	if_replace(false, n, m, cons(k, x)) -> cons(k, replace(n, m, x))
1111.22/291.78	sort(nil) -> nil
1111.22/291.78	sort(cons(n, x)) -> cons(min(cons(n, x)), sort(replace(min(cons(n, x)), n, x)))
1111.22/291.78	
1111.22/291.78	Types:
1111.22/291.78	eq :: 0':s -> 0':s -> true:false
1111.22/291.78	0' :: 0':s
1111.22/291.78	true :: true:false
1111.22/291.78	s :: 0':s -> 0':s
1111.22/291.78	false :: true:false
1111.22/291.78	le :: 0':s -> 0':s -> true:false
1111.22/291.78	min :: nil:cons -> 0':s
1111.22/291.78	cons :: 0':s -> nil:cons -> nil:cons
1111.22/291.78	nil :: nil:cons
1111.22/291.78	if_min :: true:false -> nil:cons -> 0':s
1111.22/291.78	replace :: 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	if_replace :: true:false -> 0':s -> 0':s -> nil:cons -> nil:cons
1111.22/291.78	sort :: nil:cons -> nil:cons
1111.22/291.78	hole_true:false1_0 :: true:false
1111.22/291.78	hole_0':s2_0 :: 0':s
1111.22/291.78	hole_nil:cons3_0 :: nil:cons
1111.22/291.78	gen_0':s4_0 :: Nat -> 0':s
1111.22/291.78	gen_nil:cons5_0 :: Nat -> nil:cons
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Lemmas:
1111.22/291.78	eq(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0)
1111.22/291.78	le(gen_0':s4_0(n548_0), gen_0':s4_0(n548_0)) -> true, rt in Omega(1 + n548_0)
1111.22/291.78	min(gen_nil:cons5_0(+(1, n883_0))) -> gen_0':s4_0(0), rt in Omega(1 + n883_0)
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	Generator Equations:
1111.22/291.78	gen_0':s4_0(0) <=> 0'
1111.22/291.78	gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x))
1111.22/291.78	gen_nil:cons5_0(0) <=> nil
1111.22/291.78	gen_nil:cons5_0(+(x, 1)) <=> cons(0', gen_nil:cons5_0(x))
1111.22/291.78	
1111.22/291.78	
1111.22/291.78	The following defined symbols remain to be analysed:
1111.22/291.78	sort
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(65) LowerBoundPropagationProof (FINISHED)
1111.22/291.78	Propagated lower bound.
1111.22/291.78	----------------------------------------
1111.22/291.78	
1111.22/291.78	(66)
1111.22/291.78	BOUNDS(n^2, INF)
1111.43/291.87	EOF