5.32/2.79	WORST_CASE(Omega(n^1), O(n^2))
5.32/2.80	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
5.32/2.80	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.32/2.80	
5.32/2.80	
5.32/2.80	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^2).
5.32/2.80	
5.32/2.80	(0) CpxIntTrs
5.32/2.80	(1) Koat Proof [FINISHED, 233 ms]
5.32/2.80	(2) BOUNDS(1, n^2)
5.32/2.80	(3) Loat Proof [FINISHED, 1137 ms]
5.32/2.80	(4) BOUNDS(n^1, INF)
5.32/2.80	
5.32/2.80	
5.32/2.80	----------------------------------------
5.32/2.80	
5.32/2.80	(0)
5.32/2.80	Obligation:
5.32/2.80	Complexity Int TRS consisting of the following rules:
5.32/2.80	f1(A, B, C) -> Com_1(f2(A, B, B + 1)) :|: A >= B && A >= 1 && B >= 1
5.32/2.80	f2(A, B, C) -> Com_1(f3(A, B, C)) :|: B >= C + 1
5.32/2.80	f2(A, B, C) -> Com_1(f3(A, B, C)) :|: C >= B + 1
5.32/2.80	f3(A, B, C) -> Com_1(f2(A, B, 0)) :|: A + 1 >= 0 && C >= 1 && C >= A + 1
5.32/2.80	f3(A, B, C) -> Com_1(f2(A, B, C + 1)) :|: A >= C && C + 1 >= 0
5.32/2.80	
5.32/2.80	The start-symbols are:[f1_3]
5.32/2.80	
5.32/2.80	
5.32/2.80	----------------------------------------
5.32/2.80	
5.32/2.80	(1) Koat Proof (FINISHED)
5.32/2.80	YES(?, 20*ar_0^2 + 32*ar_0*ar_1 + 280*ar_0 + 260*ar_1 + 12*ar_1^2 + 576)
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Initial complexity problem:
5.32/2.80	
5.32/2.80	1:	T:
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f1(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_1 >= ar_2 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 + 1 >= 0 /\ ar_2 >= 1 /\ ar_2 >= ar_0 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(f1(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
5.32/2.80	
5.32/2.80		start location:	koat_start
5.32/2.80	
5.32/2.80		leaf cost:	0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Repeatedly propagating knowledge in problem 1 produces the following problem:
5.32/2.80	
5.32/2.80	2:	T:
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 1)    f1(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_1 >= ar_2 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 + 1 >= 0 /\ ar_2 >= 1 /\ ar_2 >= ar_0 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(f1(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
5.32/2.80	
5.32/2.80		start location:	koat_start
5.32/2.80	
5.32/2.80		leaf cost:	0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Applied AI with 'oct' on problem 2 to obtain the following invariants:
5.32/2.80	
5.32/2.80	  For symbol f2: X_1 - X_3 + 1 >= 0 /\ X_1 - X_2 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ X_1 - 1 >= 0
5.32/2.80	
5.32/2.80	  For symbol f3: X_1 - X_3 + 1 >= 0 /\ X_1 - X_2 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 2 >= 0 /\ X_1 - 1 >= 0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	This yielded the following problem:
5.32/2.80	
5.32/2.80	3:	T:
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2) -> Com_1(f1(ar_0, ar_1, ar_2)) [ 0 <= 0 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 + 1 >= 0 /\ ar_2 >= 1 /\ ar_2 >= ar_0 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 1)    f1(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80		start location:	koat_start
5.32/2.80	
5.32/2.80		leaf cost:	0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	By chaining the transition koat_start(ar_0, ar_1, ar_2) -> Com_1(f1(ar_0, ar_1, ar_2)) [ 0 <= 0 ] with all transitions in problem 3, the following new transition is obtained:
5.32/2.80	
5.32/2.80		koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80	We thus obtain the following problem:
5.32/2.80	
5.32/2.80	4:	T:
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 1)    koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 + 1 >= 0 /\ ar_2 >= 1 /\ ar_2 >= ar_0 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 1)    f1(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80		start location:	koat_start
5.32/2.80	
5.32/2.80		leaf cost:	0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Testing for reachability in the complexity graph removes the following transition from problem 4:
5.32/2.80	
5.32/2.80		f1(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80	We thus obtain the following problem:
5.32/2.80	
5.32/2.80	5:	T:
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 + 1 >= 0 /\ ar_2 >= 1 /\ ar_2 >= ar_0 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 1)    koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80		start location:	koat_start
5.32/2.80	
5.32/2.80		leaf cost:	0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	By chaining the transition f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 ] with all transitions in problem 5, the following new transition is obtained:
5.32/2.80	
5.32/2.80		f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80	We thus obtain the following problem:
5.32/2.80	
5.32/2.80	6:	T:
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 2)    f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 + 1 >= 0 /\ ar_2 >= 1 /\ ar_2 >= ar_0 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 1)    koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80		start location:	koat_start
5.32/2.80	
5.32/2.80		leaf cost:	0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	A polynomial rank function with
5.32/2.80	
5.32/2.80		Pol(f3) = 2*V_1 - 2*V_3 + 2
5.32/2.80	
5.32/2.80		Pol(f2) = 2*V_1 - 2*V_3 + 3
5.32/2.80	
5.32/2.80	and size complexities
5.32/2.80	
5.32/2.80		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\\ ar_0 >= ar_1 /\\ ar_0 >= 1 /\\ ar_1 >= 1 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\\ ar_0 >= ar_1 /\\ ar_0 >= 1 /\\ ar_1 >= 1 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\\ ar_0 >= ar_1 /\\ ar_0 >= 1 /\\ ar_1 >= 1 ]", 0-2) = ar_1 + 1
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-2) = ?
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-2) = ?
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 + 1 >= 0 /\\ ar_2 >= 1 /\\ ar_2 >= ar_0 + 1 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 + 1 >= 0 /\\ ar_2 >= 1 /\\ ar_2 >= ar_0 + 1 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 + 1 >= 0 /\\ ar_2 >= 1 /\\ ar_2 >= ar_0 + 1 ]", 0-2) = 0
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-2) = ar_0
5.32/2.80	
5.32/2.80	orients the transitions
5.32/2.80	
5.32/2.80		f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80		f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80	weakly and the transitions
5.32/2.80	
5.32/2.80		f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80		f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80	strictly and produces the following problem:
5.32/2.80	
5.32/2.80	7:	T:
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 2)                      f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 1)                      f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 + 1 >= 0 /\ ar_2 >= 1 /\ ar_2 >= ar_0 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 2*ar_0 + 2*ar_1 + 5, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: 2*ar_0 + 2*ar_1 + 5, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 1)                      koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80		start location:	koat_start
5.32/2.80	
5.32/2.80		leaf cost:	0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Repeatedly propagating knowledge in problem 7 produces the following problem:
5.32/2.80	
5.32/2.80	8:	T:
5.32/2.80	
5.32/2.80			(Comp: ?, Cost: 2)                      f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: 2*ar_0 + 2*ar_1 + 5, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 + 1 >= 0 /\ ar_2 >= 1 /\ ar_2 >= ar_0 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 2*ar_0 + 2*ar_1 + 5, Cost: 1)    f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: 2*ar_0 + 2*ar_1 + 5, Cost: 1)    f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 1)                      koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80		start location:	koat_start
5.32/2.80	
5.32/2.80		leaf cost:	0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	A polynomial rank function with
5.32/2.80	
5.32/2.80		Pol(f2) = V_1 - V_3 + 1
5.32/2.80	
5.32/2.80	and size complexities
5.32/2.80	
5.32/2.80		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\\ ar_0 >= ar_1 /\\ ar_0 >= 1 /\\ ar_1 >= 1 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\\ ar_0 >= ar_1 /\\ ar_0 >= 1 /\\ ar_1 >= 1 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\\ ar_0 >= ar_1 /\\ ar_0 >= 1 /\\ ar_1 >= 1 ]", 0-2) = ar_1 + 1
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_2 >= ar_1 + 1 ]", 0-2) = 3*ar_0 + 3*ar_1 + 54
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-2) = 3*ar_0 + 3*ar_1 + 54
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 + 1 >= 0 /\\ ar_2 >= 1 /\\ ar_2 >= ar_0 + 1 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 + 1 >= 0 /\\ ar_2 >= 1 /\\ ar_2 >= ar_0 + 1 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_0 + 1 >= 0 /\\ ar_2 >= 1 /\\ ar_2 >= ar_0 + 1 ]", 0-2) = 0
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-0) = ar_0
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-1) = ar_1
5.32/2.80	
5.32/2.80		S("f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\\ ar_0 - ar_1 >= 0 /\\ ar_1 - 1 >= 0 /\\ ar_0 + ar_1 - 2 >= 0 /\\ ar_0 - 1 >= 0 /\\ ar_1 >= ar_2 + 1 /\\ ar_0 >= ar_2 /\\ ar_2 + 1 >= 0 ]", 0-2) = ar_0
5.32/2.80	
5.32/2.80	orients the transitions
5.32/2.80	
5.32/2.80		f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80	weakly and the transition
5.32/2.80	
5.32/2.80		f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80	strictly and produces the following problem:
5.32/2.80	
5.32/2.80	9:	T:
5.32/2.80	
5.32/2.80			(Comp: 10*ar_0^2 + 16*ar_0*ar_1 + 137*ar_0 + 127*ar_1 + 6*ar_1^2 + 280, Cost: 2)    f2(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_1 >= ar_2 + 1 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: 2*ar_0 + 2*ar_1 + 5, Cost: 1)                                                f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, 0)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 + 1 >= 0 /\ ar_2 >= 1 /\ ar_2 >= ar_0 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 2*ar_0 + 2*ar_1 + 5, Cost: 1)                                                f3(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_2 + 1)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_0 >= ar_2 /\ ar_2 + 1 >= 0 ]
5.32/2.80	
5.32/2.80			(Comp: 2*ar_0 + 2*ar_1 + 5, Cost: 1)                                                f2(ar_0, ar_1, ar_2) -> Com_1(f3(ar_0, ar_1, ar_2)) [ ar_0 - ar_2 + 1 >= 0 /\ ar_0 - ar_1 >= 0 /\ ar_1 - 1 >= 0 /\ ar_0 + ar_1 - 2 >= 0 /\ ar_0 - 1 >= 0 /\ ar_2 >= ar_1 + 1 ]
5.32/2.80	
5.32/2.80			(Comp: 1, Cost: 1)                                                                  koat_start(ar_0, ar_1, ar_2) -> Com_1(f2(ar_0, ar_1, ar_1 + 1)) [ 0 <= 0 /\ ar_0 >= ar_1 /\ ar_0 >= 1 /\ ar_1 >= 1 ]
5.32/2.80	
5.32/2.80		start location:	koat_start
5.32/2.80	
5.32/2.80		leaf cost:	0
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Complexity upper bound 20*ar_0^2 + 32*ar_0*ar_1 + 280*ar_0 + 260*ar_1 + 12*ar_1^2 + 576
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Time: 0.275 sec (SMT: 0.233 sec)
5.32/2.80	
5.32/2.80	
5.32/2.80	----------------------------------------
5.32/2.80	
5.32/2.80	(2)
5.32/2.80	BOUNDS(1, n^2)
5.32/2.80	
5.32/2.80	----------------------------------------
5.32/2.80	
5.32/2.80	(3) Loat Proof (FINISHED)
5.32/2.80	
5.32/2.80	
5.32/2.80	### Pre-processing the ITS problem ###
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Initial linear ITS problem
5.32/2.80	
5.32/2.80	   Start location: f1
5.32/2.80	
5.32/2.80	      0: f1 -> f2 : C'=1+B, [ A>=B && A>=1 && B>=1 ], cost: 1
5.32/2.80	
5.32/2.80	      1: f2 -> f3 : [ B>=1+C ], cost: 1
5.32/2.80	
5.32/2.80	      2: f2 -> f3 : [ C>=1+B ], cost: 1
5.32/2.80	
5.32/2.80	      3: f3 -> f2 : C'=0, [ 1+A>=0 && C>=1 && C>=1+A ], cost: 1
5.32/2.80	
5.32/2.80	      4: f3 -> f2 : C'=1+C, [ A>=C && 1+C>=0 ], cost: 1
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	### Simplification by acceleration and chaining ###
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Eliminated locations (on tree-shaped paths):
5.32/2.80	
5.32/2.80	   Start location: f1
5.32/2.80	
5.32/2.80	      0: f1 -> f2 : C'=1+B, [ A>=B && A>=1 && B>=1 ], cost: 1
5.32/2.80	
5.32/2.80	      5: f2 -> f2 : C'=0, [ B>=1+C && 1+A>=0 && C>=1 && C>=1+A ], cost: 2
5.32/2.80	
5.32/2.80	      6: f2 -> f2 : C'=1+C, [ B>=1+C && A>=C && 1+C>=0 ], cost: 2
5.32/2.80	
5.32/2.80	      7: f2 -> f2 : C'=0, [ C>=1+B && 1+A>=0 && C>=1 && C>=1+A ], cost: 2
5.32/2.80	
5.32/2.80	      8: f2 -> f2 : C'=1+C, [ C>=1+B && A>=C && 1+C>=0 ], cost: 2
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Accelerating simple loops of location 1.
5.32/2.80	
5.32/2.80	   Accelerating the following rules:
5.32/2.80	
5.32/2.80	      5: f2 -> f2 : C'=0, [ B>=1+C && 1+A>=0 && C>=1 && C>=1+A ], cost: 2
5.32/2.80	
5.32/2.80	      6: f2 -> f2 : C'=1+C, [ B>=1+C && A>=C && 1+C>=0 ], cost: 2
5.32/2.80	
5.32/2.80	      7: f2 -> f2 : C'=0, [ C>=1+B && 1+A>=0 && C>=1 && C>=1+A ], cost: 2
5.32/2.80	
5.32/2.80	      8: f2 -> f2 : C'=1+C, [ C>=1+B && A>=C && 1+C>=0 ], cost: 2
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	   Found no metering function for rule 5.
5.32/2.80	
5.32/2.80	   Accelerated rule 6 with backward acceleration, yielding the new rule 9.
5.32/2.80	
5.32/2.80	   Accelerated rule 6 with backward acceleration, yielding the new rule 10.
5.32/2.80	
5.32/2.80	   Found no metering function for rule 7.
5.32/2.80	
5.32/2.80	   Accelerated rule 8 with metering function 1-C+A, yielding the new rule 11.
5.32/2.80	
5.32/2.80	   Nested simple loops 5 (outer loop) and 10 (inner loop) with NONTERM, resulting in the new rules: 12, 13.
5.32/2.80	
5.32/2.80	   Nested simple loops 7 (outer loop) and 11 (inner loop) with NONTERM, resulting in the new rules: 14, 15.
5.32/2.80	
5.32/2.80	   Removing the simple loops: 5 6 7 8.
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Accelerated all simple loops using metering functions (where possible):
5.32/2.80	
5.32/2.80	   Start location: f1
5.32/2.80	
5.32/2.80	      0: f1 -> f2 : C'=1+B, [ A>=B && A>=1 && B>=1 ], cost: 1
5.32/2.80	
5.32/2.80	      9: f2 -> f2 : C'=B, [ B>=1+C && A>=C && 1+C>=0 && A>=-1+B && B>=0 ], cost: -2*C+2*B
5.32/2.80	
5.32/2.80	     10: f2 -> f2 : C'=1+A, [ B>=1+C && A>=C && 1+C>=0 && B>=1+A && 1+A>=0 ], cost: 2-2*C+2*A
5.32/2.80	
5.32/2.80	     11: f2 -> f2 : C'=1+A, [ C>=1+B && A>=C && 1+C>=0 ], cost: 2-2*C+2*A
5.32/2.80	
5.32/2.80	     12: f2 -> [3] : [ B>=1+C && A>=C && 1+C>=0 && B>=2+A && 1+A>=1 && 4-2*C+2*A>=1 ], cost: INF
5.32/2.80	
5.32/2.80	     13: f2 -> [3] : C'=0, [ B>=1+C && C>=1 && C>=1+A && B>=1 && A>=0 && B>=2+A && 4+2*A>=1 ], cost: INF
5.32/2.80	
5.32/2.80	     14: f2 -> [3] : [ C>=1+B && C>=1 && C>=1+A && 0>=1+B && A>=0 && 4+2*A>=1 ], cost: INF
5.32/2.80	
5.32/2.80	     15: f2 -> [3] : C'=1+A, [ C>=1+B && A>=C && 1+C>=0 && 1+A>=1+B && 1+A>=1 && 0>=1+B && 4+2*A>=1 ], cost: INF
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Chained accelerated rules (with incoming rules):
5.32/2.80	
5.32/2.80	   Start location: f1
5.32/2.80	
5.32/2.80	      0: f1 -> f2 : C'=1+B, [ A>=B && A>=1 && B>=1 ], cost: 1
5.32/2.80	
5.32/2.80	     16: f1 -> f2 : C'=1+A, [ A>=1 && B>=1 && A>=1+B ], cost: 1+2*A-2*B
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Removed unreachable locations (and leaf rules with constant cost):
5.32/2.80	
5.32/2.80	   Start location: f1
5.32/2.80	
5.32/2.80	     16: f1 -> f2 : C'=1+A, [ A>=1 && B>=1 && A>=1+B ], cost: 1+2*A-2*B
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	### Computing asymptotic complexity ###
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Fully simplified ITS problem
5.32/2.80	
5.32/2.80	   Start location: f1
5.32/2.80	
5.32/2.80	     16: f1 -> f2 : C'=1+A, [ A>=1 && B>=1 && A>=1+B ], cost: 1+2*A-2*B
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Computing asymptotic complexity for rule 16
5.32/2.80	
5.32/2.80	   Simplified the guard:
5.32/2.80	
5.32/2.80	     16: f1 -> f2 : C'=1+A, [ B>=1 && A>=1+B ], cost: 1+2*A-2*B
5.32/2.80	
5.32/2.80	   Solved the limit problem by the following transformations:
5.32/2.80	
5.32/2.80	      Created initial limit problem:
5.32/2.80	
5.32/2.80	      A-B (+/+!), B (+/+!), 1+2*A-2*B (+) [not solved]
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	      applying transformation rule (C) using substitution {B==1}
5.32/2.80	
5.32/2.80	      resulting limit problem:
5.32/2.80	
5.32/2.80	      1 (+/+!), -1+A (+/+!), -1+2*A (+) [not solved]
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	      applying transformation rule (C) using substitution {A==1+B}
5.32/2.80	
5.32/2.80	      resulting limit problem:
5.32/2.80	
5.32/2.80	      1 (+/+!), 1+2*B (+), B (+/+!) [not solved]
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	      applying transformation rule (B), deleting 1 (+/+!)
5.32/2.80	
5.32/2.80	      resulting limit problem:
5.32/2.80	
5.32/2.80	      1+2*B (+), B (+/+!) [not solved]
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	      applying transformation rule (D), replacing 1+2*B (+) by 2*B (+)
5.32/2.80	
5.32/2.80	      resulting limit problem:
5.32/2.80	
5.32/2.80	      2*B (+), B (+/+!) [not solved]
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	      applying transformation rule (A), replacing 2*B (+) by B (+) and 2 (+!) using + limit vector (+,+!)
5.32/2.80	
5.32/2.80	      resulting limit problem:
5.32/2.80	
5.32/2.80	      2 (+!), B (+) [not solved]
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	      applying transformation rule (B), deleting 2 (+!)
5.32/2.80	
5.32/2.80	      resulting limit problem:
5.32/2.80	
5.32/2.80	      B (+) [solved]
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	   Solution:
5.32/2.80	
5.32/2.80	      A / 1+n
5.32/2.80	
5.32/2.80	      B / 1
5.32/2.80	
5.32/2.80	   Resulting cost 1+2*n has complexity: Poly(n^1)
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Found new complexity Poly(n^1).
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	Obtained the following overall complexity (w.r.t. the length of the input n):
5.32/2.80	
5.32/2.80	   Complexity:  Poly(n^1)
5.32/2.80	
5.32/2.80	   Cpx degree:  1
5.32/2.80	
5.32/2.80	   Solved cost: 1+2*n
5.32/2.80	
5.32/2.80	   Rule cost:   1+2*A-2*B
5.32/2.80	
5.32/2.80	   Rule guard:  [ B>=1 && A>=1+B ]
5.32/2.80	
5.32/2.80	
5.32/2.80	
5.32/2.80	WORST_CASE(Omega(n^1),?)
5.32/2.80	
5.32/2.80	
5.32/2.80	----------------------------------------
5.32/2.80	
5.32/2.80	(4)
5.32/2.80	BOUNDS(n^1, INF)
5.39/2.82	EOF