6.71/2.88	WORST_CASE(Omega(n^1), O(n^1))
6.71/2.89	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
6.71/2.89	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.71/2.89	
6.71/2.89	
6.71/2.89	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1).
6.71/2.89	
6.71/2.89	(0) CpxIntTrs
6.71/2.89	(1) Koat Proof [FINISHED, 715 ms]
6.71/2.89	(2) BOUNDS(1, n^1)
6.71/2.89	(3) Loat Proof [FINISHED, 1211 ms]
6.71/2.89	(4) BOUNDS(n^1, INF)
6.71/2.89	
6.71/2.89	
6.71/2.89	----------------------------------------
6.71/2.89	
6.71/2.89	(0)
6.71/2.89	Obligation:
6.71/2.89	Complexity Int TRS consisting of the following rules:
6.71/2.89	start(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, 0, F, D, H)) :|: 0 >= A && B >= C && B <= C && D >= A && D <= A && E >= F && E <= F && G >= H && G <= H
6.71/2.89	start(A, B, C, D, E, F, G, H) -> Com_1(cut(A, B, C, D, 0, F, D - 1, H)) :|: A >= 2 && B >= C && B <= C && D >= A && D <= A && E >= F && E <= F && G >= H && G <= H
6.71/2.89	start(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, 0, F, D - 1, H)) :|: D >= 1 && D <= 1 && B >= C && B <= C && A >= 1 && A <= 1 && E >= F && E <= F && G >= H && G <= H
6.71/2.89	start(A, B, C, D, E, F, G, H) -> Com_1(cut(A, 0, C, D, 1, F, D - 1, H)) :|: A >= 2 && B >= C && B <= C && D >= A && D <= A && E >= F && E <= F && G >= H && G <= H
6.71/2.89	start(A, B, C, D, E, F, G, H) -> Com_1(stop(A, 0, C, D, 0, F, D - 1, H)) :|: D >= 1 && D <= 1 && B >= C && B <= C && A >= 1 && A <= 1 && E >= F && E <= F && G >= H && G <= H
6.71/2.89	cut(A, B, C, D, E, F, G, H) -> Com_1(cut(A, B, C, D, E - 1, F, G - 1, H)) :|: G >= 2 && E >= 2 && G >= 1 && E >= 0 && A >= G + 1 && A >= G + E && D >= A && D <= A
6.71/2.89	cut(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, E - 1, F, G - 1, H)) :|: E >= 2 && E >= 0 && A >= 2 && A >= 1 + E && G >= 1 && G <= 1 && D >= A && D <= A
6.71/2.89	cut(A, B, C, D, E, F, G, H) -> Com_1(cut(A, B, C, D, 0, F, G - 1, H)) :|: G >= 2 && 1 >= E && G >= 1 && E >= 0 && A >= G + 1 && A >= G + E && D >= A && D <= A
6.71/2.89	cut(A, B, C, D, E, F, G, H) -> Com_1(stop(A, B, C, D, 0, F, G - 1, H)) :|: 1 >= E && E >= 0 && A >= 2 && A >= 1 + E && G >= 1 && G <= 1 && D >= A && D <= A
6.71/2.89	cut(A, B, C, D, E, F, G, H) -> Com_1(cut(A, E, C, D, 1 + E, F, G - 1, H)) :|: G >= 2 && A >= E + 2 && G >= 1 && E >= 0 && A >= G + 1 && A >= G + E && D >= A && D <= A
6.71/2.89	cut(A, B, C, D, E, F, G, H) -> Com_1(stop(A, E, C, D, 1 + E, F, G - 1, H)) :|: A >= E + 2 && E >= 0 && A >= 2 && A >= 1 + E && G >= 1 && G <= 1 && D >= A && D <= A
6.71/2.89	cut(A, B, C, D, E, F, G, H) -> Com_1(cut(A, E, C, D, 0, F, G - 1, H)) :|: G >= 2 && E + 1 >= A && G >= 1 && E >= 0 && A >= G + 1 && A >= G + E && D >= A && D <= A
6.71/2.89	cut(A, B, C, D, E, F, G, H) -> Com_1(stop(A, E, C, D, 0, F, G - 1, H)) :|: A >= 1 && A >= 2 && G >= 1 && G <= 1 && E + 1 >= A && E + 1 <= A && D >= A && D <= A
6.71/2.89	start0(A, B, C, D, E, F, G, H) -> Com_1(start(A, C, C, A, F, F, H, H)) :|: TRUE
6.71/2.89	
6.71/2.89	The start-symbols are:[start0_8]
6.71/2.89	
6.71/2.89	
6.71/2.89	----------------------------------------
6.71/2.89	
6.71/2.89	(1) Koat Proof (FINISHED)
6.71/2.89	YES(?, 3*ar_0 + 10)
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Initial complexity problem:
6.71/2.89	
6.71/2.89	1:	T:
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3, ar_7)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, 0, ar_2, ar_3, 1, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, 0, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_4 >= 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_4 >= 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ 1 >= ar_4 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ 1 >= ar_4 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_0 >= ar_4 + 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= ar_4 + 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_4, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_4 + 1 >= ar_0 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= 1 /\ ar_0 >= 2 /\ ar_6 = 1 /\ ar_4 + 1 = ar_0 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start(ar_0, ar_2, ar_2, ar_0, ar_5, ar_5, ar_7, ar_7))
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7)) [ 0 <= 0 ]
6.71/2.89	
6.71/2.89		start location:	koat_start
6.71/2.89	
6.71/2.89		leaf cost:	0
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Testing for reachability in the complexity graph removes the following transition from problem 1:
6.71/2.89	
6.71/2.89		cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_4, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_4 + 1 >= ar_0 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89	We thus obtain the following problem:
6.71/2.89	
6.71/2.89	2:	T:
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_4 >= 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_4 >= 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= 1 /\ ar_0 >= 2 /\ ar_6 = 1 /\ ar_4 + 1 = ar_0 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= ar_4 + 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_0 >= ar_4 + 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ 1 >= ar_4 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ 1 >= ar_4 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, 0, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, 0, ar_2, ar_3, 1, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3, ar_7)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start(ar_0, ar_2, ar_2, ar_0, ar_5, ar_5, ar_7, ar_7))
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7)) [ 0 <= 0 ]
6.71/2.89	
6.71/2.89		start location:	koat_start
6.71/2.89	
6.71/2.89		leaf cost:	0
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Repeatedly propagating knowledge in problem 2 produces the following problem:
6.71/2.89	
6.71/2.89	3:	T:
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_4 >= 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_4 >= 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= 1 /\ ar_0 >= 2 /\ ar_6 = 1 /\ ar_4 + 1 = ar_0 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= ar_4 + 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_0 >= ar_4 + 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ 1 >= ar_4 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ 1 >= ar_4 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, 0, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, 0, ar_2, ar_3, 1, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3, ar_7)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start(ar_0, ar_2, ar_2, ar_0, ar_5, ar_5, ar_7, ar_7))
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7)) [ 0 <= 0 ]
6.71/2.89	
6.71/2.89		start location:	koat_start
6.71/2.89	
6.71/2.89		leaf cost:	0
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	A polynomial rank function with
6.71/2.89	
6.71/2.89		Pol(cut) = 1
6.71/2.89	
6.71/2.89		Pol(stop) = 0
6.71/2.89	
6.71/2.89		Pol(start) = 1
6.71/2.89	
6.71/2.89		Pol(start0) = 1
6.71/2.89	
6.71/2.89		Pol(koat_start) = 1
6.71/2.89	
6.71/2.89	orients all transitions weakly and the transitions
6.71/2.89	
6.71/2.89		cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= ar_4 + 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89		cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= 1 /\ ar_0 >= 2 /\ ar_6 = 1 /\ ar_4 + 1 = ar_0 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89		cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ 1 >= ar_4 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89		cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_4 >= 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89	strictly and produces the following problem:
6.71/2.89	
6.71/2.89	4:	T:
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_4 >= 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_4 >= 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= 1 /\ ar_0 >= 2 /\ ar_6 = 1 /\ ar_4 + 1 = ar_0 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= ar_4 + 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_0 >= ar_4 + 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ 1 >= ar_4 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ?, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ 1 >= ar_4 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, 0, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, 0, ar_2, ar_3, 1, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3, ar_7)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start(ar_0, ar_2, ar_2, ar_0, ar_5, ar_5, ar_7, ar_7))
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7)) [ 0 <= 0 ]
6.71/2.89	
6.71/2.89		start location:	koat_start
6.71/2.89	
6.71/2.89		leaf cost:	0
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	A polynomial rank function with
6.71/2.89	
6.71/2.89		Pol(cut) = V_7
6.71/2.89	
6.71/2.89		Pol(stop) = V_7
6.71/2.89	
6.71/2.89		Pol(start) = V_1
6.71/2.89	
6.71/2.89		Pol(start0) = V_1
6.71/2.89	
6.71/2.89		Pol(koat_start) = V_1
6.71/2.89	
6.71/2.89	orients all transitions weakly and the transitions
6.71/2.89	
6.71/2.89		cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_0 >= ar_4 + 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89		cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ 1 >= ar_4 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89		cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_4 >= 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89	strictly and produces the following problem:
6.71/2.89	
6.71/2.89	5:	T:
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_4 >= 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ar_0, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, ar_4 - 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_4 >= 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= 1 /\ ar_0 >= 2 /\ ar_6 = 1 /\ ar_4 + 1 = ar_0 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_0 >= ar_4 + 2 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ar_0, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_4, ar_2, ar_3, ar_4 + 1, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ ar_0 >= ar_4 + 2 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ 1 >= ar_4 /\ ar_4 >= 0 /\ ar_0 >= 2 /\ ar_0 >= ar_4 + 1 /\ ar_6 = 1 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: ar_0, Cost: 1)    cut(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_6 - 1, ar_7)) [ ar_6 >= 2 /\ 1 >= ar_4 /\ ar_6 >= 1 /\ ar_4 >= 0 /\ ar_0 >= ar_6 + 1 /\ ar_0 >= ar_6 + ar_4 /\ ar_3 = ar_0 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, 0, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, 0, ar_2, ar_3, 1, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_3 = 1 /\ ar_1 = ar_2 /\ ar_0 = 1 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(cut(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3 - 1, ar_7)) [ ar_0 >= 2 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(stop(ar_0, ar_1, ar_2, ar_3, 0, ar_5, ar_3, ar_7)) [ 0 >= ar_0 /\ ar_1 = ar_2 /\ ar_3 = ar_0 /\ ar_4 = ar_5 /\ ar_6 = ar_7 ]
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 1)       start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start(ar_0, ar_2, ar_2, ar_0, ar_5, ar_5, ar_7, ar_7))
6.71/2.89	
6.71/2.89			(Comp: 1, Cost: 0)       koat_start(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3, ar_4, ar_5, ar_6, ar_7)) [ 0 <= 0 ]
6.71/2.89	
6.71/2.89		start location:	koat_start
6.71/2.89	
6.71/2.89		leaf cost:	0
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Complexity upper bound 3*ar_0 + 10
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Time: 0.646 sec (SMT: 0.526 sec)
6.71/2.89	
6.71/2.89	
6.71/2.89	----------------------------------------
6.71/2.89	
6.71/2.89	(2)
6.71/2.89	BOUNDS(1, n^1)
6.71/2.89	
6.71/2.89	----------------------------------------
6.71/2.89	
6.71/2.89	(3) Loat Proof (FINISHED)
6.71/2.89	
6.71/2.89	
6.71/2.89	### Pre-processing the ITS problem ###
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Initial linear ITS problem
6.71/2.89	
6.71/2.89	   Start location: start0
6.71/2.89	
6.71/2.89	      0: start -> stop : E'=0, G'=D, [ 0>=A && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      1: start -> cut : E'=0, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      2: start -> stop : E'=0, G'=-1+D, [ D==1 && B==C && A==1 && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      3: start -> cut : B'=0, E'=1, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      4: start -> stop : B'=0, E'=0, G'=-1+D, [ D==1 && B==C && A==1 && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      5: cut -> cut : E'=-1+E, G'=-1+G, [ G>=2 && E>=2 && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      6: cut -> stop : E'=-1+E, G'=-1+G, [ E>=2 && E>=0 && A>=2 && A>=1+E && G==1 && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      7: cut -> cut : E'=0, G'=-1+G, [ G>=2 && 1>=E && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      8: cut -> stop : E'=0, G'=-1+G, [ 1>=E && E>=0 && A>=2 && A>=1+E && G==1 && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      9: cut -> cut : B'=E, E'=1+E, G'=-1+G, [ G>=2 && A>=2+E && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	     10: cut -> stop : B'=E, E'=1+E, G'=-1+G, [ A>=2+E && E>=0 && A>=2 && A>=1+E && G==1 && D==A ], cost: 1
6.71/2.89	
6.71/2.89	     11: cut -> cut : B'=E, E'=0, G'=-1+G, [ G>=2 && 1+E>=A && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	     12: cut -> stop : B'=E, E'=0, G'=-1+G, [ A>=1 && A>=2 && G==1 && 1+E==A && D==A ], cost: 1
6.71/2.89	
6.71/2.89	     13: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Removed unreachable and leaf rules:
6.71/2.89	
6.71/2.89	   Start location: start0
6.71/2.89	
6.71/2.89	      1: start -> cut : E'=0, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      3: start -> cut : B'=0, E'=1, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      5: cut -> cut : E'=-1+E, G'=-1+G, [ G>=2 && E>=2 && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      7: cut -> cut : E'=0, G'=-1+G, [ G>=2 && 1>=E && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      9: cut -> cut : B'=E, E'=1+E, G'=-1+G, [ G>=2 && A>=2+E && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	     11: cut -> cut : B'=E, E'=0, G'=-1+G, [ G>=2 && 1+E>=A && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	     13: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Removed rules with unsatisfiable guard:
6.71/2.89	
6.71/2.89	   Start location: start0
6.71/2.89	
6.71/2.89	      1: start -> cut : E'=0, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      3: start -> cut : B'=0, E'=1, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      5: cut -> cut : E'=-1+E, G'=-1+G, [ G>=2 && E>=2 && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      7: cut -> cut : E'=0, G'=-1+G, [ G>=2 && 1>=E && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      9: cut -> cut : B'=E, E'=1+E, G'=-1+G, [ G>=2 && A>=2+E && G>=1 && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	     13: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Simplified all rules, resulting in:
6.71/2.89	
6.71/2.89	   Start location: start0
6.71/2.89	
6.71/2.89	      1: start -> cut : E'=0, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      3: start -> cut : B'=0, E'=1, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      5: cut -> cut : E'=-1+E, G'=-1+G, [ G>=2 && E>=2 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      7: cut -> cut : E'=0, G'=-1+G, [ G>=2 && 1>=E && E>=0 && A>=1+G && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      9: cut -> cut : B'=E, E'=1+E, G'=-1+G, [ G>=2 && A>=2+E && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	     13: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	### Simplification by acceleration and chaining ###
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Accelerating simple loops of location 1.
6.71/2.89	
6.71/2.89	   Accelerating the following rules:
6.71/2.89	
6.71/2.89	      5: cut -> cut : E'=-1+E, G'=-1+G, [ G>=2 && E>=2 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      7: cut -> cut : E'=0, G'=-1+G, [ G>=2 && 1>=E && E>=0 && A>=1+G && D==A ], cost: 1
6.71/2.89	
6.71/2.89	      9: cut -> cut : B'=E, E'=1+E, G'=-1+G, [ G>=2 && A>=2+E && E>=0 && A>=1+G && A>=G+E && D==A ], cost: 1
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	   Accelerated rule 5 with metering function -1+G (after adding E>=G), yielding the new rule 14.
6.71/2.89	
6.71/2.89	   Accelerated rule 5 with metering function -1+E (after adding E<=G), yielding the new rule 15.
6.71/2.89	
6.71/2.89	   Accelerated rule 7 with metering function -1+G, yielding the new rule 16.
6.71/2.89	
6.71/2.89	   Accelerated rule 9 with metering function -1+G, yielding the new rule 17.
6.71/2.89	
6.71/2.89	   Removing the simple loops: 5 7 9.
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Accelerated all simple loops using metering functions (where possible):
6.71/2.89	
6.71/2.89	   Start location: start0
6.71/2.89	
6.71/2.89	      1: start -> cut : E'=0, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      3: start -> cut : B'=0, E'=1, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	     14: cut -> cut : E'=1-G+E, G'=1, [ G>=2 && E>=2 && A>=1+G && A>=G+E && D==A && E>=G ], cost: -1+G
6.71/2.89	
6.71/2.89	     15: cut -> cut : E'=1, G'=1+G-E, [ G>=2 && E>=2 && A>=1+G && A>=G+E && D==A && E<=G ], cost: -1+E
6.71/2.89	
6.71/2.89	     16: cut -> cut : E'=0, G'=1, [ G>=2 && 1>=E && E>=0 && A>=1+G && D==A ], cost: -1+G
6.71/2.89	
6.71/2.89	     17: cut -> cut : B'=-2+G+E, E'=-1+G+E, G'=1, [ G>=2 && A>=2+E && E>=0 && A>=1+G && A>=G+E && D==A ], cost: -1+G
6.71/2.89	
6.71/2.89	     13: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Chained accelerated rules (with incoming rules):
6.71/2.89	
6.71/2.89	   Start location: start0
6.71/2.89	
6.71/2.89	      1: start -> cut : E'=0, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	      3: start -> cut : B'=0, E'=1, G'=-1+D, [ A>=2 && B==C && D==A && E==F && G==H ], cost: 1
6.71/2.89	
6.71/2.89	     18: start -> cut : E'=0, G'=1, [ A>=2 && B==C && D==A && E==F && G==H && -1+D>=2 ], cost: -1+D
6.71/2.89	
6.71/2.89	     19: start -> cut : B'=0, E'=0, G'=1, [ A>=2 && B==C && D==A && E==F && G==H && -1+D>=2 ], cost: -1+D
6.71/2.89	
6.71/2.89	     20: start -> cut : B'=-3+D, E'=-2+D, G'=1, [ A>=2 && B==C && D==A && E==F && G==H && -1+D>=2 ], cost: -1+D
6.71/2.89	
6.71/2.89	     21: start -> cut : B'=-2+D, E'=-1+D, G'=1, [ B==C && D==A && E==F && G==H && -1+D>=2 && A>=3 ], cost: -1+D
6.71/2.89	
6.71/2.89	     13: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Removed unreachable locations (and leaf rules with constant cost):
6.71/2.89	
6.71/2.89	   Start location: start0
6.71/2.89	
6.71/2.89	     18: start -> cut : E'=0, G'=1, [ A>=2 && B==C && D==A && E==F && G==H && -1+D>=2 ], cost: -1+D
6.71/2.89	
6.71/2.89	     19: start -> cut : B'=0, E'=0, G'=1, [ A>=2 && B==C && D==A && E==F && G==H && -1+D>=2 ], cost: -1+D
6.71/2.89	
6.71/2.89	     20: start -> cut : B'=-3+D, E'=-2+D, G'=1, [ A>=2 && B==C && D==A && E==F && G==H && -1+D>=2 ], cost: -1+D
6.71/2.89	
6.71/2.89	     21: start -> cut : B'=-2+D, E'=-1+D, G'=1, [ B==C && D==A && E==F && G==H && -1+D>=2 && A>=3 ], cost: -1+D
6.71/2.89	
6.71/2.89	     13: start0 -> start : B'=C, D'=A, E'=F, G'=H, [], cost: 1
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Eliminated locations (on tree-shaped paths):
6.71/2.89	
6.71/2.89	   Start location: start0
6.71/2.89	
6.71/2.89	     22: start0 -> cut : B'=C, D'=A, E'=0, G'=1, [ -1+A>=2 ], cost: A
6.71/2.89	
6.71/2.89	     23: start0 -> cut : B'=0, D'=A, E'=0, G'=1, [ -1+A>=2 ], cost: A
6.71/2.89	
6.71/2.89	     24: start0 -> cut : B'=-3+A, D'=A, E'=-2+A, G'=1, [ -1+A>=2 ], cost: A
6.71/2.89	
6.71/2.89	     25: start0 -> cut : B'=-2+A, D'=A, E'=-1+A, G'=1, [ -1+A>=2 ], cost: A
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	### Computing asymptotic complexity ###
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Fully simplified ITS problem
6.71/2.89	
6.71/2.89	   Start location: start0
6.71/2.89	
6.71/2.89	     25: start0 -> cut : B'=-2+A, D'=A, E'=-1+A, G'=1, [ -1+A>=2 ], cost: A
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Computing asymptotic complexity for rule 25
6.71/2.89	
6.71/2.89	   Solved the limit problem by the following transformations:
6.71/2.89	
6.71/2.89	      Created initial limit problem:
6.71/2.89	
6.71/2.89	      A (+), -2+A (+/+!) [not solved]
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	      removing all constraints (solved by SMT)
6.71/2.89	
6.71/2.89	      resulting limit problem: [solved]
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	      applying transformation rule (C) using substitution {A==n}
6.71/2.89	
6.71/2.89	      resulting limit problem:
6.71/2.89	
6.71/2.89	      [solved]
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	   Solution:
6.71/2.89	
6.71/2.89	      A / n
6.71/2.89	
6.71/2.89	   Resulting cost n has complexity: Poly(n^1)
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Found new complexity Poly(n^1).
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	Obtained the following overall complexity (w.r.t. the length of the input n):
6.71/2.89	
6.71/2.89	   Complexity:  Poly(n^1)
6.71/2.89	
6.71/2.89	   Cpx degree:  1
6.71/2.89	
6.71/2.89	   Solved cost: n
6.71/2.89	
6.71/2.89	   Rule cost:   A
6.71/2.89	
6.71/2.89	   Rule guard:  [ -1+A>=2 ]
6.71/2.89	
6.71/2.89	
6.71/2.89	
6.71/2.89	WORST_CASE(Omega(n^1),?)
6.71/2.89	
6.71/2.89	
6.71/2.89	----------------------------------------
6.71/2.89	
6.71/2.89	(4)
6.71/2.89	BOUNDS(n^1, INF)
6.91/2.92	EOF