4.50/2.13	WORST_CASE(Omega(n^1), O(n^1))
4.50/2.14	proof of /export/starexec/sandbox/benchmark/theBenchmark.koat
4.50/2.14	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.50/2.14	
4.50/2.14	
4.50/2.14	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1).
4.50/2.14	
4.50/2.14	(0) CpxIntTrs
4.50/2.14	(1) Koat Proof [FINISHED, 101 ms]
4.50/2.14	(2) BOUNDS(1, n^1)
4.50/2.14	(3) Loat Proof [FINISHED, 506 ms]
4.50/2.14	(4) BOUNDS(n^1, INF)
4.50/2.14	
4.50/2.14	
4.50/2.14	----------------------------------------
4.50/2.14	
4.50/2.14	(0)
4.50/2.14	Obligation:
4.50/2.14	Complexity Int TRS consisting of the following rules:
4.50/2.14	start(A, B, C, D) -> Com_1(stop1(A, B, C, D)) :|: A >= 0 && B >= 0 && C >= 0 && D >= 0 && D <= 0
4.50/2.14	start(A, B, C, D) -> Com_1(cont1(A, B, C, D)) :|: D >= 1 && A >= 0 && B >= 0 && C >= 0 && D >= 0 && A >= D
4.50/2.14	cont1(A, B, C, D) -> Com_1(stop2(A, B, 1, D - 1)) :|: D >= 1 && B >= 0 && A >= D && C >= 0 && C <= 0
4.50/2.14	cont1(A, B, C, D) -> Com_1(a(A, B, C - 1, D)) :|: C >= 1 && D >= 1 && C >= 0 && B >= 0 && A >= D
4.50/2.14	a(A, B, C, D) -> Com_1(b(A, B, E, D - 1)) :|: A >= D && B >= 0 && C >= 0 && D >= 1
4.50/2.14	b(A, B, C, D) -> Com_1(start(A, B, C, D)) :|: C >= 0 && D >= 0 && B >= 0 && A >= D + 1
4.50/2.14	b(A, B, C, D) -> Com_1(stop3(A, B, C, D)) :|: 0 >= C + 1 && D >= 0 && B >= 0 && A >= D + 1
4.50/2.14	start0(A, B, C, D) -> Com_1(start(A, B, B, A)) :|: A >= 0 && B >= 0
4.50/2.14	
4.50/2.14	The start-symbols are:[start0_4]
4.50/2.14	
4.50/2.14	
4.50/2.14	----------------------------------------
4.50/2.14	
4.50/2.14	(1) Koat Proof (FINISHED)
4.50/2.14	YES(?, 16*ar_0 + 4)
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Initial complexity problem:
4.50/2.14	
4.50/2.14	1:	T:
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_1, ar_0)) [ ar_0 >= 0 /\ ar_1 >= 0 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.50/2.14	
4.50/2.14		start location:	koat_start
4.50/2.14	
4.50/2.14		leaf cost:	0
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Repeatedly propagating knowledge in problem 1 produces the following problem:
4.50/2.14	
4.50/2.14	2:	T:
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_1, ar_0)) [ ar_0 >= 0 /\ ar_1 >= 0 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.50/2.14	
4.50/2.14		start location:	koat_start
4.50/2.14	
4.50/2.14		leaf cost:	0
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	A polynomial rank function with
4.50/2.14	
4.50/2.14		Pol(start) = 1
4.50/2.14	
4.50/2.14		Pol(stop1) = 0
4.50/2.14	
4.50/2.14		Pol(cont1) = 1
4.50/2.14	
4.50/2.14		Pol(stop2) = 0
4.50/2.14	
4.50/2.14		Pol(a) = 1
4.50/2.14	
4.50/2.14		Pol(b) = 1
4.50/2.14	
4.50/2.14		Pol(stop3) = 0
4.50/2.14	
4.50/2.14		Pol(start0) = 1
4.50/2.14	
4.50/2.14		Pol(koat_start) = 1
4.50/2.14	
4.50/2.14	orients all transitions weakly and the transitions
4.50/2.14	
4.50/2.14		start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ]
4.50/2.14	
4.50/2.14		cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ]
4.50/2.14	
4.50/2.14		b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14	strictly and produces the following problem:
4.50/2.14	
4.50/2.14	3:	T:
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 1)    cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ]
4.50/2.14	
4.50/2.14			(Comp: ?, Cost: 1)    b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 1)    b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 1)    start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_1, ar_0)) [ ar_0 >= 0 /\ ar_1 >= 0 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.50/2.14	
4.50/2.14		start location:	koat_start
4.50/2.14	
4.50/2.14		leaf cost:	0
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	A polynomial rank function with
4.50/2.14	
4.50/2.14		Pol(start) = 4*V_4
4.50/2.14	
4.50/2.14		Pol(stop1) = 4*V_4
4.50/2.14	
4.50/2.14		Pol(cont1) = 4*V_4 - 1
4.50/2.14	
4.50/2.14		Pol(stop2) = 4*V_4
4.50/2.14	
4.50/2.14		Pol(a) = 4*V_4 - 2
4.50/2.14	
4.50/2.14		Pol(b) = 4*V_4 + 1
4.50/2.14	
4.50/2.14		Pol(stop3) = 4*V_4
4.50/2.14	
4.50/2.14		Pol(start0) = 4*V_1
4.50/2.14	
4.50/2.14		Pol(koat_start) = 4*V_1
4.50/2.14	
4.50/2.14	orients all transitions weakly and the transitions
4.50/2.14	
4.50/2.14		start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14		cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14		b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14		a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ]
4.50/2.14	
4.50/2.14	strictly and produces the following problem:
4.50/2.14	
4.50/2.14	4:	T:
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 1)         start(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop1(ar_0, ar_1, ar_2, ar_3)) [ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 = 0 ]
4.50/2.14	
4.50/2.14			(Comp: 4*ar_0, Cost: 1)    start(ar_0, ar_1, ar_2, ar_3) -> Com_1(cont1(ar_0, ar_1, ar_2, ar_3)) [ ar_3 >= 1 /\ ar_0 >= 0 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 1)         cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop2(ar_0, ar_1, 1, ar_3 - 1)) [ ar_3 >= 1 /\ ar_1 >= 0 /\ ar_0 >= ar_3 /\ ar_2 = 0 ]
4.50/2.14	
4.50/2.14			(Comp: 4*ar_0, Cost: 1)    cont1(ar_0, ar_1, ar_2, ar_3) -> Com_1(a(ar_0, ar_1, ar_2 - 1, ar_3)) [ ar_2 >= 1 /\ ar_3 >= 1 /\ ar_2 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 ]
4.50/2.14	
4.50/2.14			(Comp: 4*ar_0, Cost: 1)    a(ar_0, ar_1, ar_2, ar_3) -> Com_1(b(ar_0, ar_1, e, ar_3 - 1)) [ ar_0 >= ar_3 /\ ar_1 >= 0 /\ ar_2 >= 0 /\ ar_3 >= 1 ]
4.50/2.14	
4.50/2.14			(Comp: 4*ar_0, Cost: 1)    b(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_2, ar_3)) [ ar_2 >= 0 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 1)         b(ar_0, ar_1, ar_2, ar_3) -> Com_1(stop3(ar_0, ar_1, ar_2, ar_3)) [ 0 >= ar_2 + 1 /\ ar_3 >= 0 /\ ar_1 >= 0 /\ ar_0 >= ar_3 + 1 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 1)         start0(ar_0, ar_1, ar_2, ar_3) -> Com_1(start(ar_0, ar_1, ar_1, ar_0)) [ ar_0 >= 0 /\ ar_1 >= 0 ]
4.50/2.14	
4.50/2.14			(Comp: 1, Cost: 0)         koat_start(ar_0, ar_1, ar_2, ar_3) -> Com_1(start0(ar_0, ar_1, ar_2, ar_3)) [ 0 <= 0 ]
4.50/2.14	
4.50/2.14		start location:	koat_start
4.50/2.14	
4.50/2.14		leaf cost:	0
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Complexity upper bound 16*ar_0 + 4
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Time: 0.150 sec (SMT: 0.138 sec)
4.50/2.14	
4.50/2.14	
4.50/2.14	----------------------------------------
4.50/2.14	
4.50/2.14	(2)
4.50/2.14	BOUNDS(1, n^1)
4.50/2.14	
4.50/2.14	----------------------------------------
4.50/2.14	
4.50/2.14	(3) Loat Proof (FINISHED)
4.50/2.14	
4.50/2.14	
4.50/2.14	### Pre-processing the ITS problem ###
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Initial linear ITS problem
4.50/2.14	
4.50/2.14	   Start location: start0
4.50/2.14	
4.50/2.14	      0: start -> stop1 : [ A>=0 && B>=0 && C>=0 && D==0 ], cost: 1
4.50/2.14	
4.50/2.14	      1: start -> cont1 : [ D>=1 && A>=0 && B>=0 && C>=0 && D>=0 && A>=D ], cost: 1
4.50/2.14	
4.50/2.14	      2: cont1 -> stop2 : C'=1, D'=-1+D, [ D>=1 && B>=0 && A>=D && C==0 ], cost: 1
4.50/2.14	
4.50/2.14	      3: cont1 -> a : C'=-1+C, [ C>=1 && D>=1 && C>=0 && B>=0 && A>=D ], cost: 1
4.50/2.14	
4.50/2.14	      4: a -> b : C'=free, D'=-1+D, [ A>=D && B>=0 && C>=0 && D>=1 ], cost: 1
4.50/2.14	
4.50/2.14	      5: b -> start : [ C>=0 && D>=0 && B>=0 && A>=1+D ], cost: 1
4.50/2.14	
4.50/2.14	      6: b -> stop3 : [ 0>=1+C && D>=0 && B>=0 && A>=1+D ], cost: 1
4.50/2.14	
4.50/2.14	      7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Removed unreachable and leaf rules:
4.50/2.14	
4.50/2.14	   Start location: start0
4.50/2.14	
4.50/2.14	      1: start -> cont1 : [ D>=1 && A>=0 && B>=0 && C>=0 && D>=0 && A>=D ], cost: 1
4.50/2.14	
4.50/2.14	      3: cont1 -> a : C'=-1+C, [ C>=1 && D>=1 && C>=0 && B>=0 && A>=D ], cost: 1
4.50/2.14	
4.50/2.14	      4: a -> b : C'=free, D'=-1+D, [ A>=D && B>=0 && C>=0 && D>=1 ], cost: 1
4.50/2.14	
4.50/2.14	      5: b -> start : [ C>=0 && D>=0 && B>=0 && A>=1+D ], cost: 1
4.50/2.14	
4.50/2.14	      7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Simplified all rules, resulting in:
4.50/2.14	
4.50/2.14	   Start location: start0
4.50/2.14	
4.50/2.14	      1: start -> cont1 : [ D>=1 && A>=0 && B>=0 && C>=0 && A>=D ], cost: 1
4.50/2.14	
4.50/2.14	      3: cont1 -> a : C'=-1+C, [ C>=1 && D>=1 && B>=0 && A>=D ], cost: 1
4.50/2.14	
4.50/2.14	      4: a -> b : C'=free, D'=-1+D, [ A>=D && B>=0 && C>=0 && D>=1 ], cost: 1
4.50/2.14	
4.50/2.14	      5: b -> start : [ C>=0 && D>=0 && B>=0 && A>=1+D ], cost: 1
4.50/2.14	
4.50/2.14	      7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	### Simplification by acceleration and chaining ###
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Eliminated locations (on linear paths):
4.50/2.14	
4.50/2.14	   Start location: start0
4.50/2.14	
4.50/2.14	     10: start -> start : C'=free, D'=-1+D, [ D>=1 && A>=0 && B>=0 && A>=D && C>=1 && free>=0 ], cost: 4
4.50/2.14	
4.50/2.14	      7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Accelerating simple loops of location 0.
4.50/2.14	
4.50/2.14	   Accelerating the following rules:
4.50/2.14	
4.50/2.14	     10: start -> start : C'=free, D'=-1+D, [ D>=1 && A>=0 && B>=0 && A>=D && C>=1 && free>=0 ], cost: 4
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	   Accelerated rule 10 with metering function D (after strengthening guard), yielding the new rule 11.
4.50/2.14	
4.50/2.14	   Removing the simple loops:.
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Accelerated all simple loops using metering functions (where possible):
4.50/2.14	
4.50/2.14	   Start location: start0
4.50/2.14	
4.50/2.14	     10: start -> start : C'=free, D'=-1+D, [ D>=1 && A>=0 && B>=0 && A>=D && C>=1 && free>=0 ], cost: 4
4.50/2.14	
4.50/2.14	     11: start -> start : C'=free, D'=0, [ D>=1 && A>=0 && B>=0 && A>=D && C>=1 && free>=1 ], cost: 4*D
4.50/2.14	
4.50/2.14	      7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Chained accelerated rules (with incoming rules):
4.50/2.14	
4.50/2.14	   Start location: start0
4.50/2.14	
4.50/2.14	      7: start0 -> start : C'=B, D'=A, [ A>=0 && B>=0 ], cost: 1
4.50/2.14	
4.50/2.14	     12: start0 -> start : C'=free, D'=-1+A, [ A>=1 && B>=1 && free>=0 ], cost: 5
4.50/2.14	
4.50/2.14	     13: start0 -> start : C'=free, D'=0, [ A>=1 && B>=1 && free>=1 ], cost: 1+4*A
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Removed unreachable locations (and leaf rules with constant cost):
4.50/2.14	
4.50/2.14	   Start location: start0
4.50/2.14	
4.50/2.14	     13: start0 -> start : C'=free, D'=0, [ A>=1 && B>=1 && free>=1 ], cost: 1+4*A
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	### Computing asymptotic complexity ###
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Fully simplified ITS problem
4.50/2.14	
4.50/2.14	   Start location: start0
4.50/2.14	
4.50/2.14	     13: start0 -> start : C'=free, D'=0, [ A>=1 && B>=1 && free>=1 ], cost: 1+4*A
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Computing asymptotic complexity for rule 13
4.50/2.14	
4.50/2.14	   Solved the limit problem by the following transformations:
4.50/2.14	
4.50/2.14	      Created initial limit problem:
4.50/2.14	
4.50/2.14	      free (+/+!), 1+4*A (+), A (+/+!), B (+/+!) [not solved]
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	      removing all constraints (solved by SMT)
4.50/2.14	
4.50/2.14	      resulting limit problem: [solved]
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	      applying transformation rule (C) using substitution {free==n,A==n,B==n}
4.50/2.14	
4.50/2.14	      resulting limit problem:
4.50/2.14	
4.50/2.14	      [solved]
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	   Solution:
4.50/2.14	
4.50/2.14	      free / n
4.50/2.14	
4.50/2.14	      A / n
4.50/2.14	
4.50/2.14	      B / n
4.50/2.14	
4.50/2.14	   Resulting cost 1+4*n has complexity: Poly(n^1)
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Found new complexity Poly(n^1).
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	Obtained the following overall complexity (w.r.t. the length of the input n):
4.50/2.14	
4.50/2.14	   Complexity:  Poly(n^1)
4.50/2.14	
4.50/2.14	   Cpx degree:  1
4.50/2.14	
4.50/2.14	   Solved cost: 1+4*n
4.50/2.14	
4.50/2.14	   Rule cost:   1+4*A
4.50/2.14	
4.50/2.14	   Rule guard:  [ A>=1 && B>=1 && free>=1 ]
4.50/2.14	
4.50/2.14	
4.50/2.14	
4.50/2.14	WORST_CASE(Omega(n^1),?)
4.50/2.14	
4.50/2.14	
4.50/2.14	----------------------------------------
4.50/2.14	
4.50/2.14	(4)
4.50/2.14	BOUNDS(n^1, INF)
4.66/2.15	EOF