MAYBE Initial complexity problem: 1: T: (?, 1) f14(a, b, c, d, e, f, g) -> f14(a - 1, b - 1, c + 1, h, e, f, g) [ a >= 1 /\ h >= 1 ] (?, 1) f14(a, b, c, d, e, f, g) -> f14(a - 1, b, c, h, e, f, g) [ 0 >= h /\ a >= 1 /\ a >= b + 1 ] (?, 1) f24(a, b, c, d, e, f, g) -> f24(a, b, c, d, e, f, g) (?, 1) f26(a, b, c, d, e, f, g) -> f29(a, b, c, d, e, f, g) (?, 1) f14(a, b, c, d, e, f, g) -> f24(a, b, c, d, e, f, g) [ 0 >= a ] (1, 1) f0(a, b, c, d, e, f, g) -> f14(2*i + 1, h, 0, d, h, 2*i + 1, i) [ h >= 1 /\ 2*i >= 0 ] start location: f0 leaf cost: 0 Slicing away variables that do not contribute to conditions from problem 1 leaves variables [a, b]. We thus obtain the following problem: 2: T: (1, 1) f0(a, b) -> f14(2*i + 1, h) [ h >= 1 /\ 2*i >= 0 ] (?, 1) f14(a, b) -> f24(a, b) [ 0 >= a ] (?, 1) f26(a, b) -> f29(a, b) (?, 1) f24(a, b) -> f24(a, b) (?, 1) f14(a, b) -> f14(a - 1, b) [ 0 >= h /\ a >= 1 /\ a >= b + 1 ] (?, 1) f14(a, b) -> f14(a - 1, b - 1) [ a >= 1 /\ h >= 1 ] start location: f0 leaf cost: 0 Repeatedly removing leaves of the complexity graph in problem 2 produces the following problem: 3: T: (1, 1) f0(a, b) -> f14(2*i + 1, h) [ h >= 1 /\ 2*i >= 0 ] (?, 1) f14(a, b) -> f24(a, b) [ 0 >= a ] (?, 1) f24(a, b) -> f24(a, b) (?, 1) f14(a, b) -> f14(a - 1, b) [ 0 >= h /\ a >= 1 /\ a >= b + 1 ] (?, 1) f14(a, b) -> f14(a - 1, b - 1) [ a >= 1 /\ h >= 1 ] start location: f0 leaf cost: 1 A polynomial rank function with Pol(f0) = 1 Pol(f14) = 1 Pol(f24) = 0 orients all transitions weakly and the transition f14(a, b) -> f24(a, b) [ 0 >= a ] strictly and produces the following problem: 4: T: (1, 1) f0(a, b) -> f14(2*i + 1, h) [ h >= 1 /\ 2*i >= 0 ] (1, 1) f14(a, b) -> f24(a, b) [ 0 >= a ] (?, 1) f24(a, b) -> f24(a, b) (?, 1) f14(a, b) -> f14(a - 1, b) [ 0 >= h /\ a >= 1 /\ a >= b + 1 ] (?, 1) f14(a, b) -> f14(a - 1, b - 1) [ a >= 1 /\ h >= 1 ] start location: f0 leaf cost: 1 Applied AI with 'oct' on problem 4 to obtain the following invariants: For symbol f24: -X_1 >= 0 This yielded the following problem: 5: T: (?, 1) f14(a, b) -> f14(a - 1, b - 1) [ a >= 1 /\ h >= 1 ] (?, 1) f14(a, b) -> f14(a - 1, b) [ 0 >= h /\ a >= 1 /\ a >= b + 1 ] (?, 1) f24(a, b) -> f24(a, b) [ -a >= 0 ] (1, 1) f14(a, b) -> f24(a, b) [ 0 >= a ] (1, 1) f0(a, b) -> f14(2*i + 1, h) [ h >= 1 /\ 2*i >= 0 ] start location: f0 leaf cost: 1 By chaining the transition f14(a, b) -> f24(a, b) [ 0 >= a ] with all transitions in problem 5, the following new transition is obtained: f14(a, b) -> f24(a, b) [ 0 >= a /\ -a >= 0 ] We thus obtain the following problem: 6: T: (1, 2) f14(a, b) -> f24(a, b) [ 0 >= a /\ -a >= 0 ] (?, 1) f14(a, b) -> f14(a - 1, b - 1) [ a >= 1 /\ h >= 1 ] (?, 1) f14(a, b) -> f14(a - 1, b) [ 0 >= h /\ a >= 1 /\ a >= b + 1 ] (?, 1) f24(a, b) -> f24(a, b) [ -a >= 0 ] (1, 1) f0(a, b) -> f14(2*i + 1, h) [ h >= 1 /\ 2*i >= 0 ] start location: f0 leaf cost: 1 Complexity upper bound ? Time: 0.446 sec (SMT: 0.422 sec)