MAYBE

Initial complexity problem:
1:	T:
		(1, 1)    f3(a, b) -> f0(0, b)
		(?, 1)    f0(a, b) -> f0(a, b - 1) [ b >= 1 ]
		(?, 1)    f4(a, b) -> f4(a, b)
		(?, 1)    f0(a, b) -> f4(-1, b) [ 0 >= b ]
	start location:	f3
	leaf cost:	0

A polynomial rank function with
	Pol(f3) = 1
	Pol(f0) = 1
	Pol(f4) = 0
orients all transitions weakly and the transition
	f0(a, b) -> f4(-1, b) [ 0 >= b ]
strictly and produces the following problem:
2:	T:
		(1, 1)    f3(a, b) -> f0(0, b)
		(?, 1)    f0(a, b) -> f0(a, b - 1) [ b >= 1 ]
		(?, 1)    f4(a, b) -> f4(a, b)
		(1, 1)    f0(a, b) -> f4(-1, b) [ 0 >= b ]
	start location:	f3
	leaf cost:	0

A polynomial rank function with
	Pol(f3) = V_2
	Pol(f0) = V_2
	Pol(f4) = V_2
orients all transitions weakly and the transition
	f0(a, b) -> f0(a, b - 1) [ b >= 1 ]
strictly and produces the following problem:
3:	T:
		(1, 1)    f3(a, b) -> f0(0, b)
		(b, 1)    f0(a, b) -> f0(a, b - 1) [ b >= 1 ]
		(?, 1)    f4(a, b) -> f4(a, b)
		(1, 1)    f0(a, b) -> f4(-1, b) [ 0 >= b ]
	start location:	f3
	leaf cost:	0

Applied AI with 'oct' on problem 3 to obtain the following invariants:
  For symbol f0: -X_1 >= 0 /\ X_1 >= 0
  For symbol f4: -X_2 >= 0 /\ X_1 - X_2 + 1 >= 0 /\ -X_1 - X_2 - 1 >= 0 /\ -X_1 - 1 >= 0 /\ X_1 + 1 >= 0


This yielded the following problem:
4:	T:
		(1, 1)    f0(a, b) -> f4(-1, b) [ -a >= 0 /\ a >= 0 /\ 0 >= b ]
		(?, 1)    f4(a, b) -> f4(a, b) [ -b >= 0 /\ a - b + 1 >= 0 /\ -a - b - 1 >= 0 /\ -a - 1 >= 0 /\ a + 1 >= 0 ]
		(b, 1)    f0(a, b) -> f0(a, b - 1) [ -a >= 0 /\ a >= 0 /\ b >= 1 ]
		(1, 1)    f3(a, b) -> f0(0, b)
	start location:	f3
	leaf cost:	0

By chaining the transition f0(a, b) -> f4(-1, b) [ -a >= 0 /\ a >= 0 /\ 0 >= b ] with all transitions in problem 4, the following new transition is obtained:
	f0(a, b) -> f4(-1, b) [ -a >= 0 /\ a >= 0 /\ 0 >= b /\ -b >= 0 /\ 0 >= 0 ]
We thus obtain the following problem:
5:	T:
		(1, 2)    f0(a, b) -> f4(-1, b) [ -a >= 0 /\ a >= 0 /\ 0 >= b /\ -b >= 0 /\ 0 >= 0 ]
		(?, 1)    f4(a, b) -> f4(a, b) [ -b >= 0 /\ a - b + 1 >= 0 /\ -a - b - 1 >= 0 /\ -a - 1 >= 0 /\ a + 1 >= 0 ]
		(b, 1)    f0(a, b) -> f0(a, b - 1) [ -a >= 0 /\ a >= 0 /\ b >= 1 ]
		(1, 1)    f3(a, b) -> f0(0, b)
	start location:	f3
	leaf cost:	0

Complexity upper bound ?

Time: 0.341 sec (SMT: 0.322 sec)