5.07/2.48	WORST_CASE(Omega(n^1), O(n^1))
5.07/2.49	proof of /export/starexec/sandbox2/benchmark/theBenchmark.koat
5.07/2.49	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
5.07/2.49	
5.07/2.49	
5.07/2.49	The runtime complexity of the given CpxIntTrs could be proven to be BOUNDS(n^1, n^1).
5.07/2.49	
5.07/2.49	(0) CpxIntTrs
5.07/2.49	(1) Koat Proof [FINISHED, 123 ms]
5.07/2.49	(2) BOUNDS(1, n^1)
5.07/2.49	(3) Loat Proof [FINISHED, 691 ms]
5.07/2.49	(4) BOUNDS(n^1, INF)
5.07/2.49	
5.07/2.49	
5.07/2.49	----------------------------------------
5.07/2.49	
5.07/2.49	(0)
5.07/2.49	Obligation:
5.07/2.49	Complexity Int TRS consisting of the following rules:
5.07/2.49	f0(A, B, C, D, E) -> Com_1(f1(A, B, C, D, E)) :|: TRUE
5.07/2.49	f1(A, B, C, D, E) -> Com_1(f1(A, B + 1, C, D, E)) :|: A >= B + 1
5.07/2.49	f1(A, B, C, D, E) -> Com_1(f2(A, B, B, D, E)) :|: B >= A
5.07/2.49	f2(A, B, C, D, E) -> Com_1(f2(A, B, C - 1, D, E)) :|: C >= 1
5.07/2.49	f2(A, B, C, D, E) -> Com_1(f3(A, B, C, C, E)) :|: 0 >= C
5.07/2.49	f3(A, B, C, D, E) -> Com_1(f3(A, B, C, D + 1, E)) :|: A >= D + 1
5.07/2.49	f3(A, B, C, D, E) -> Com_1(f4(A, B, C, D, D)) :|: D >= A
5.07/2.49	f4(A, B, C, D, E) -> Com_1(f4(A, B, C, D, E - 1)) :|: E >= 1
5.07/2.49	
5.07/2.49	The start-symbols are:[f0_5]
5.07/2.49	
5.07/2.49	
5.07/2.49	----------------------------------------
5.07/2.49	
5.07/2.49	(1) Koat Proof (FINISHED)
5.07/2.49	YES(?, 88*ar_0 + 85*ar_1 + 10)
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Initial complexity problem:
5.07/2.49	
5.07/2.49	1:	T:
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.07/2.49	
5.07/2.49		start location:	koat_start
5.07/2.49	
5.07/2.49		leaf cost:	0
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Repeatedly propagating knowledge in problem 1 produces the following problem:
5.07/2.49	
5.07/2.49	2:	T:
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 1)    f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.07/2.49	
5.07/2.49		start location:	koat_start
5.07/2.49	
5.07/2.49		leaf cost:	0
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	A polynomial rank function with
5.07/2.49	
5.07/2.49		Pol(f0) = 3
5.07/2.49	
5.07/2.49		Pol(f1) = 3
5.07/2.49	
5.07/2.49		Pol(f2) = 2
5.07/2.49	
5.07/2.49		Pol(f3) = 1
5.07/2.49	
5.07/2.49		Pol(f4) = 0
5.07/2.49	
5.07/2.49		Pol(koat_start) = 3
5.07/2.49	
5.07/2.49	orients all transitions weakly and the transitions
5.07/2.49	
5.07/2.49		f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]
5.07/2.49	
5.07/2.49		f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]
5.07/2.49	
5.07/2.49		f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]
5.07/2.49	
5.07/2.49	strictly and produces the following problem:
5.07/2.49	
5.07/2.49	3:	T:
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 1)    f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)    f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)    f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)    f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)    f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 0)    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.07/2.49	
5.07/2.49		start location:	koat_start
5.07/2.49	
5.07/2.49		leaf cost:	0
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	A polynomial rank function with
5.07/2.49	
5.07/2.49		Pol(f0) = V_1 - V_2
5.07/2.49	
5.07/2.49		Pol(f1) = V_1 - V_2
5.07/2.49	
5.07/2.49		Pol(f2) = V_1 - V_2
5.07/2.49	
5.07/2.49		Pol(f3) = V_1 - V_2
5.07/2.49	
5.07/2.49		Pol(f4) = V_1 - V_2
5.07/2.49	
5.07/2.49		Pol(koat_start) = V_1 - V_2
5.07/2.49	
5.07/2.49	orients all transitions weakly and the transition
5.07/2.49	
5.07/2.49		f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]
5.07/2.49	
5.07/2.49	strictly and produces the following problem:
5.07/2.49	
5.07/2.49	4:	T:
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 1)              f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.07/2.49	
5.07/2.49			(Comp: ar_0 + ar_1, Cost: 1)    f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)              f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)              f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)              f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)              f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)              f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)              f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 0)              koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.07/2.49	
5.07/2.49		start location:	koat_start
5.07/2.49	
5.07/2.49		leaf cost:	0
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	A polynomial rank function with
5.07/2.49	
5.07/2.49		Pol(f3) = V_1 - V_4
5.07/2.49	
5.07/2.49	and size complexities
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-1) = ar_1
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-2) = ar_2
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-3) = ?
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-4) = ?
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-3) = ?
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-4) = ?
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-3) = ?
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-3) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-2) = ar_2
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4
5.07/2.49	
5.07/2.49	orients the transitions
5.07/2.49	
5.07/2.49		f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]
5.07/2.49	
5.07/2.49	weakly and the transition
5.07/2.49	
5.07/2.49		f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]
5.07/2.49	
5.07/2.49	strictly and produces the following problem:
5.07/2.49	
5.07/2.49	5:	T:
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 1)                  f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.07/2.49	
5.07/2.49			(Comp: ar_0 + ar_1, Cost: 1)        f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)                  f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)                  f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)                  f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]
5.07/2.49	
5.07/2.49			(Comp: 9*ar_0 + 6*ar_1, Cost: 1)    f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)                  f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: ?, Cost: 1)                  f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 0)                  koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.07/2.49	
5.07/2.49		start location:	koat_start
5.07/2.49	
5.07/2.49		leaf cost:	0
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	A polynomial rank function with
5.07/2.49	
5.07/2.49		Pol(f4) = V_5
5.07/2.49	
5.07/2.49		Pol(f2) = V_3
5.07/2.49	
5.07/2.49	and size complexities
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-1) = ar_1
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-2) = ar_2
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-3) = 11*ar_0 + 11*ar_1
5.07/2.49	
5.07/2.49		S("f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]", 0-4) = 11*ar_0 + 11*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-3) = 11*ar_0 + 11*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]", 0-4) = 11*ar_0 + 11*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-3) = 11*ar_0 + 11*ar_1
5.07/2.49	
5.07/2.49		S("f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-3) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-2) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-1) = 2*ar_0 + 2*ar_1
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-2) = ar_2
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]", 0-4) = ar_4
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-0) = ar_0
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-1) = ar_1
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-2) = ar_2
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-3) = ar_3
5.07/2.49	
5.07/2.49		S("f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))", 0-4) = ar_4
5.07/2.49	
5.07/2.49	orients the transitions
5.07/2.49	
5.07/2.49		f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]
5.07/2.49	
5.07/2.49		f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]
5.07/2.49	
5.07/2.49	weakly and the transitions
5.07/2.49	
5.07/2.49		f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]
5.07/2.49	
5.07/2.49		f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]
5.07/2.49	
5.07/2.49	strictly and produces the following problem:
5.07/2.49	
5.07/2.49	6:	T:
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 1)                    f0(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1, ar_2, ar_3, ar_4))
5.07/2.49	
5.07/2.49			(Comp: ar_0 + ar_1, Cost: 1)          f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f1(ar_0, ar_1 + 1, ar_2, ar_3, ar_4)) [ ar_0 >= ar_1 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)                    f1(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_1, ar_3, ar_4)) [ ar_1 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: 39*ar_0 + 39*ar_1, Cost: 1)    f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f2(ar_0, ar_1, ar_2 - 1, ar_3, ar_4)) [ ar_2 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)                    f2(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_2, ar_4)) [ 0 >= ar_2 ]
5.07/2.49	
5.07/2.49			(Comp: 9*ar_0 + 6*ar_1, Cost: 1)      f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f3(ar_0, ar_1, ar_2, ar_3 + 1, ar_4)) [ ar_0 >= ar_3 + 1 ]
5.07/2.49	
5.07/2.49			(Comp: 3, Cost: 1)                    f3(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_3)) [ ar_3 >= ar_0 ]
5.07/2.49	
5.07/2.49			(Comp: 39*ar_0 + 39*ar_1, Cost: 1)    f4(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f4(ar_0, ar_1, ar_2, ar_3, ar_4 - 1)) [ ar_4 >= 1 ]
5.07/2.49	
5.07/2.49			(Comp: 1, Cost: 0)                    koat_start(ar_0, ar_1, ar_2, ar_3, ar_4) -> Com_1(f0(ar_0, ar_1, ar_2, ar_3, ar_4)) [ 0 <= 0 ]
5.07/2.49	
5.07/2.49		start location:	koat_start
5.07/2.49	
5.07/2.49		leaf cost:	0
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Complexity upper bound 88*ar_0 + 85*ar_1 + 10
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Time: 0.175 sec (SMT: 0.143 sec)
5.07/2.49	
5.07/2.49	
5.07/2.49	----------------------------------------
5.07/2.49	
5.07/2.49	(2)
5.07/2.49	BOUNDS(1, n^1)
5.07/2.49	
5.07/2.49	----------------------------------------
5.07/2.49	
5.07/2.49	(3) Loat Proof (FINISHED)
5.07/2.49	
5.07/2.49	
5.07/2.49	### Pre-processing the ITS problem ###
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Initial linear ITS problem
5.07/2.49	
5.07/2.49	   Start location: f0
5.07/2.49	
5.07/2.49	      0: f0 -> f1 : [], cost: 1
5.07/2.49	
5.07/2.49	      1: f1 -> f1 : B'=1+B, [ A>=1+B ], cost: 1
5.07/2.49	
5.07/2.49	      2: f1 -> f2 : C'=B, [ B>=A ], cost: 1
5.07/2.49	
5.07/2.49	      3: f2 -> f2 : C'=-1+C, [ C>=1 ], cost: 1
5.07/2.49	
5.07/2.49	      4: f2 -> f3 : D'=C, [ 0>=C ], cost: 1
5.07/2.49	
5.07/2.49	      5: f3 -> f3 : D'=1+D, [ A>=1+D ], cost: 1
5.07/2.49	
5.07/2.49	      6: f3 -> f4 : E'=D, [ D>=A ], cost: 1
5.07/2.49	
5.07/2.49	      7: f4 -> f4 : E'=-1+E, [ E>=1 ], cost: 1
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	### Simplification by acceleration and chaining ###
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Accelerating simple loops of location 1.
5.07/2.49	
5.07/2.49	   Accelerating the following rules:
5.07/2.49	
5.07/2.49	      1: f1 -> f1 : B'=1+B, [ A>=1+B ], cost: 1
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	   Accelerated rule 1 with metering function A-B, yielding the new rule 8.
5.07/2.49	
5.07/2.49	   Removing the simple loops: 1.
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Accelerating simple loops of location 2.
5.07/2.49	
5.07/2.49	   Accelerating the following rules:
5.07/2.49	
5.07/2.49	      3: f2 -> f2 : C'=-1+C, [ C>=1 ], cost: 1
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	   Accelerated rule 3 with metering function C, yielding the new rule 9.
5.07/2.49	
5.07/2.49	   Removing the simple loops: 3.
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Accelerating simple loops of location 3.
5.07/2.49	
5.07/2.49	   Accelerating the following rules:
5.07/2.49	
5.07/2.49	      5: f3 -> f3 : D'=1+D, [ A>=1+D ], cost: 1
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	   Accelerated rule 5 with metering function -D+A, yielding the new rule 10.
5.07/2.49	
5.07/2.49	   Removing the simple loops: 5.
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Accelerating simple loops of location 4.
5.07/2.49	
5.07/2.49	   Accelerating the following rules:
5.07/2.49	
5.07/2.49	      7: f4 -> f4 : E'=-1+E, [ E>=1 ], cost: 1
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	   Accelerated rule 7 with metering function E, yielding the new rule 11.
5.07/2.49	
5.07/2.49	   Removing the simple loops: 7.
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Accelerated all simple loops using metering functions (where possible):
5.07/2.49	
5.07/2.49	   Start location: f0
5.07/2.49	
5.07/2.49	      0: f0 -> f1 : [], cost: 1
5.07/2.49	
5.07/2.49	      2: f1 -> f2 : C'=B, [ B>=A ], cost: 1
5.07/2.49	
5.07/2.49	      8: f1 -> f1 : B'=A, [ A>=1+B ], cost: A-B
5.07/2.49	
5.07/2.49	      4: f2 -> f3 : D'=C, [ 0>=C ], cost: 1
5.07/2.49	
5.07/2.49	      9: f2 -> f2 : C'=0, [ C>=1 ], cost: C
5.07/2.49	
5.07/2.49	      6: f3 -> f4 : E'=D, [ D>=A ], cost: 1
5.07/2.49	
5.07/2.49	     10: f3 -> f3 : D'=A, [ A>=1+D ], cost: -D+A
5.07/2.49	
5.07/2.49	     11: f4 -> f4 : E'=0, [ E>=1 ], cost: E
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Chained accelerated rules (with incoming rules):
5.07/2.49	
5.07/2.49	   Start location: f0
5.07/2.49	
5.07/2.49	      0: f0 -> f1 : [], cost: 1
5.07/2.49	
5.07/2.49	     12: f0 -> f1 : B'=A, [ A>=1+B ], cost: 1+A-B
5.07/2.49	
5.07/2.49	      2: f1 -> f2 : C'=B, [ B>=A ], cost: 1
5.07/2.49	
5.07/2.49	     13: f1 -> f2 : C'=0, [ B>=A && B>=1 ], cost: 1+B
5.07/2.49	
5.07/2.49	      4: f2 -> f3 : D'=C, [ 0>=C ], cost: 1
5.07/2.49	
5.07/2.49	     14: f2 -> f3 : D'=A, [ 0>=C && A>=1+C ], cost: 1-C+A
5.07/2.49	
5.07/2.49	      6: f3 -> f4 : E'=D, [ D>=A ], cost: 1
5.07/2.49	
5.07/2.49	     15: f3 -> f4 : E'=0, [ D>=A && D>=1 ], cost: 1+D
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Removed unreachable locations (and leaf rules with constant cost):
5.07/2.49	
5.07/2.49	   Start location: f0
5.07/2.49	
5.07/2.49	      0: f0 -> f1 : [], cost: 1
5.07/2.49	
5.07/2.49	     12: f0 -> f1 : B'=A, [ A>=1+B ], cost: 1+A-B
5.07/2.49	
5.07/2.49	      2: f1 -> f2 : C'=B, [ B>=A ], cost: 1
5.07/2.49	
5.07/2.49	     13: f1 -> f2 : C'=0, [ B>=A && B>=1 ], cost: 1+B
5.07/2.49	
5.07/2.49	      4: f2 -> f3 : D'=C, [ 0>=C ], cost: 1
5.07/2.49	
5.07/2.49	     14: f2 -> f3 : D'=A, [ 0>=C && A>=1+C ], cost: 1-C+A
5.07/2.49	
5.07/2.49	     15: f3 -> f4 : E'=0, [ D>=A && D>=1 ], cost: 1+D
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Eliminated locations (on tree-shaped paths):
5.07/2.49	
5.07/2.49	   Start location: f0
5.07/2.49	
5.07/2.49	     16: f0 -> f2 : C'=B, [ B>=A ], cost: 2
5.07/2.49	
5.07/2.49	     17: f0 -> f2 : C'=0, [ B>=A && B>=1 ], cost: 2+B
5.07/2.49	
5.07/2.49	     18: f0 -> f2 : B'=A, C'=A, [ A>=1+B ], cost: 2+A-B
5.07/2.49	
5.07/2.49	     19: f0 -> f2 : B'=A, C'=0, [ A>=1+B && A>=1 ], cost: 2+2*A-B
5.07/2.49	
5.07/2.49	     20: f2 -> f4 : D'=A, E'=0, [ 0>=C && A>=1+C && A>=1 ], cost: 2-C+2*A
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Eliminated locations (on tree-shaped paths):
5.07/2.49	
5.07/2.49	   Start location: f0
5.07/2.49	
5.07/2.49	     21: f0 -> f4 : C'=0, D'=A, E'=0, [ B>=A && B>=1 && A>=1 ], cost: 4+2*A+B
5.07/2.49	
5.07/2.49	     22: f0 -> f4 : B'=A, C'=0, D'=A, E'=0, [ A>=1+B && A>=1 ], cost: 4+4*A-B
5.07/2.49	
5.07/2.49	     23: f0 -> [9] : [ A>=1+B ], cost: 2+A-B
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	### Computing asymptotic complexity ###
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Fully simplified ITS problem
5.07/2.49	
5.07/2.49	   Start location: f0
5.07/2.49	
5.07/2.49	     21: f0 -> f4 : C'=0, D'=A, E'=0, [ B>=A && B>=1 && A>=1 ], cost: 4+2*A+B
5.07/2.49	
5.07/2.49	     22: f0 -> f4 : B'=A, C'=0, D'=A, E'=0, [ A>=1+B && A>=1 ], cost: 4+4*A-B
5.07/2.49	
5.07/2.49	     23: f0 -> [9] : [ A>=1+B ], cost: 2+A-B
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Computing asymptotic complexity for rule 21
5.07/2.49	
5.07/2.49	   Solved the limit problem by the following transformations:
5.07/2.49	
5.07/2.49	      Created initial limit problem:
5.07/2.49	
5.07/2.49	      4+2*A+B (+), A (+/+!), 1-A+B (+/+!), B (+/+!) [not solved]
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	      removing all constraints (solved by SMT)
5.07/2.49	
5.07/2.49	      resulting limit problem: [solved]
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	      applying transformation rule (C) using substitution {A==n,B==1+n}
5.07/2.49	
5.07/2.49	      resulting limit problem:
5.07/2.49	
5.07/2.49	      [solved]
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	   Solution:
5.07/2.49	
5.07/2.49	      A / n
5.07/2.49	
5.07/2.49	      B / 1+n
5.07/2.49	
5.07/2.49	   Resulting cost 5+3*n has complexity: Poly(n^1)
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Found new complexity Poly(n^1).
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	Obtained the following overall complexity (w.r.t. the length of the input n):
5.07/2.49	
5.07/2.49	   Complexity:  Poly(n^1)
5.07/2.49	
5.07/2.49	   Cpx degree:  1
5.07/2.49	
5.07/2.49	   Solved cost: 5+3*n
5.07/2.49	
5.07/2.49	   Rule cost:   4+2*A+B
5.07/2.49	
5.07/2.49	   Rule guard:  [ B>=A && B>=1 && A>=1 ]
5.07/2.49	
5.07/2.49	
5.07/2.49	
5.07/2.49	WORST_CASE(Omega(n^1),?)
5.07/2.49	
5.07/2.49	
5.07/2.49	----------------------------------------
5.07/2.49	
5.07/2.49	(4)
5.07/2.49	BOUNDS(n^1, INF)
5.27/2.51	EOF