MAYBE Initial complexity problem: 1: T: (?, 1) f2(a, b, c, d, e, f, g, h, i, j, k) -> f2(a, l, m, n, f, f, g, h, i, j, k) [ a >= 2 ] (?, 1) f2(a, b, c, d, e, f, g, h, i, j, k) -> f1(a, l, m, d, e, f, n, h, i, j, k) [ 1 >= a ] (1, 1) f300(a, b, c, d, e, f, g, h, i, j, k) -> f2(a, l, m, n, o, o, g, h, p, q, r) [ h >= 1 ] (1, 1) f300(a, b, c, d, e, f, g, h, i, j, k) -> f1(a, l, m, d, n, p, o, h, q, n, r) [ 0 >= h ] start location: f300 leaf cost: 0 Slicing away variables that do not contribute to conditions from problem 1 leaves variables [a, h]. We thus obtain the following problem: 2: T: (1, 1) f300(a, h) -> f1(a, h) [ 0 >= h ] (1, 1) f300(a, h) -> f2(a, h) [ h >= 1 ] (?, 1) f2(a, h) -> f1(a, h) [ 1 >= a ] (?, 1) f2(a, h) -> f2(a, h) [ a >= 2 ] start location: f300 leaf cost: 0 Repeatedly removing leaves of the complexity graph in problem 2 produces the following problem: 3: T: (1, 1) f300(a, h) -> f2(a, h) [ h >= 1 ] (?, 1) f2(a, h) -> f2(a, h) [ a >= 2 ] start location: f300 leaf cost: 2 Applied AI with 'oct' on problem 3 to obtain the following invariants: For symbol f2: X_2 - 1 >= 0 This yielded the following problem: 4: T: (?, 1) f2(a, h) -> f2(a, h) [ h - 1 >= 0 /\ a >= 2 ] (1, 1) f300(a, h) -> f2(a, h) [ h >= 1 ] start location: f300 leaf cost: 2 By chaining the transition f300(a, h) -> f2(a, h) [ h >= 1 ] with all transitions in problem 4, the following new transition is obtained: f300(a, h) -> f2(a, h) [ h >= 1 /\ h - 1 >= 0 /\ a >= 2 ] We thus obtain the following problem: 5: T: (1, 2) f300(a, h) -> f2(a, h) [ h >= 1 /\ h - 1 >= 0 /\ a >= 2 ] (?, 1) f2(a, h) -> f2(a, h) [ h - 1 >= 0 /\ a >= 2 ] start location: f300 leaf cost: 2 Complexity upper bound ? Time: 0.134 sec (SMT: 0.123 sec)