MAYBE Initial complexity problem: 1: T: (?, 1) f18(a, b, c, d, e, f, g, h, i, j, k) -> f24(a, b, c, d, e, f, g, h, i, j, k) [ 0 >= a ] (?, 1) f32(a, b, c, d, e, f, g, h, i, j, k) -> f32(a, b, c, d, e, f, g, h, i, j, k) (?, 1) f34(a, b, c, d, e, f, g, h, i, j, k) -> f37(a, b, c, d, e, f, g, h, i, j, k) (?, 1) f24(a, b, c, d, e, f, g, h, i, j, k) -> f32(a, l, c, d, e, f, g, h, i, j, k) [ a >= 1 ] (?, 1) f24(a, b, c, d, e, f, g, h, i, j, k) -> f32(a, m, c, l, l, f, g, h, i, j, k) [ 0 >= a /\ c + 999 >= l ] (?, 1) f24(a, b, c, d, e, f, g, h, i, j, k) -> f32(1, m, c, l, l, f, g, h, i, j, k) [ 0 >= a /\ l >= c + 1000 ] (?, 1) f18(a, b, c, d, e, f, g, h, i, j, k) -> f24(0, b, l, d, e, l, g, h, i, j, k) [ a >= 1 ] (1, 1) f0(a, b, c, d, e, f, g, h, i, j, k) -> f18(1, b, c, d, e, f, l, m, i, j, k) [ 0 >= m ] (1, 1) f0(a, b, c, d, e, f, g, h, i, j, k) -> f18(1, b, c, d, e, f, l, 0, 1, m, m) [ m >= 1 /\ n >= 1 ] (1, 1) f0(a, b, c, d, e, f, g, h, i, j, k) -> f32(1, b, c, d, e, f, l, 0, 1, m, m) [ 0 >= m /\ n >= 1 ] start location: f0 leaf cost: 0 Slicing away variables that do not contribute to conditions from problem 1 leaves variables [a, c]. We thus obtain the following problem: 2: T: (1, 1) f0(a, c) -> f32(1, c) [ 0 >= m /\ n >= 1 ] (1, 1) f0(a, c) -> f18(1, c) [ m >= 1 /\ n >= 1 ] (1, 1) f0(a, c) -> f18(1, c) [ 0 >= m ] (?, 1) f18(a, c) -> f24(0, l) [ a >= 1 ] (?, 1) f24(a, c) -> f32(1, c) [ 0 >= a /\ l >= c + 1000 ] (?, 1) f24(a, c) -> f32(a, c) [ 0 >= a /\ c + 999 >= l ] (?, 1) f24(a, c) -> f32(a, c) [ a >= 1 ] (?, 1) f34(a, c) -> f37(a, c) (?, 1) f32(a, c) -> f32(a, c) (?, 1) f18(a, c) -> f24(a, c) [ 0 >= a ] 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, c) -> f32(1, c) [ 0 >= m /\ n >= 1 ] (1, 1) f0(a, c) -> f18(1, c) [ m >= 1 /\ n >= 1 ] (1, 1) f0(a, c) -> f18(1, c) [ 0 >= m ] (?, 1) f18(a, c) -> f24(0, l) [ a >= 1 ] (?, 1) f24(a, c) -> f32(1, c) [ 0 >= a /\ l >= c + 1000 ] (?, 1) f24(a, c) -> f32(a, c) [ 0 >= a /\ c + 999 >= l ] (?, 1) f24(a, c) -> f32(a, c) [ a >= 1 ] (?, 1) f32(a, c) -> f32(a, c) (?, 1) f18(a, c) -> f24(a, c) [ 0 >= a ] start location: f0 leaf cost: 1 Testing for reachability in the complexity graph removes the following transitions from problem 3: f24(a, c) -> f32(a, c) [ a >= 1 ] f18(a, c) -> f24(a, c) [ 0 >= a ] We thus obtain the following problem: 4: T: (?, 1) f24(a, c) -> f32(a, c) [ 0 >= a /\ c + 999 >= l ] (?, 1) f24(a, c) -> f32(1, c) [ 0 >= a /\ l >= c + 1000 ] (?, 1) f18(a, c) -> f24(0, l) [ a >= 1 ] (?, 1) f32(a, c) -> f32(a, c) (1, 1) f0(a, c) -> f18(1, c) [ 0 >= m ] (1, 1) f0(a, c) -> f18(1, c) [ m >= 1 /\ n >= 1 ] (1, 1) f0(a, c) -> f32(1, c) [ 0 >= m /\ n >= 1 ] start location: f0 leaf cost: 1 Repeatedly propagating knowledge in problem 4 produces the following problem: 5: T: (2, 1) f24(a, c) -> f32(a, c) [ 0 >= a /\ c + 999 >= l ] (2, 1) f24(a, c) -> f32(1, c) [ 0 >= a /\ l >= c + 1000 ] (2, 1) f18(a, c) -> f24(0, l) [ a >= 1 ] (?, 1) f32(a, c) -> f32(a, c) (1, 1) f0(a, c) -> f18(1, c) [ 0 >= m ] (1, 1) f0(a, c) -> f18(1, c) [ m >= 1 /\ n >= 1 ] (1, 1) f0(a, c) -> f32(1, c) [ 0 >= m /\ n >= 1 ] start location: f0 leaf cost: 1 Applied AI with 'oct' on problem 5 to obtain the following invariants: For symbol f18: -X_1 + 1 >= 0 /\ X_1 - 1 >= 0 For symbol f24: -X_1 >= 0 /\ X_1 >= 0 For symbol f32: -X_1 + 1 >= 0 /\ X_1 >= 0 This yielded the following problem: 6: T: (1, 1) f0(a, c) -> f32(1, c) [ 0 >= m /\ n >= 1 ] (1, 1) f0(a, c) -> f18(1, c) [ m >= 1 /\ n >= 1 ] (1, 1) f0(a, c) -> f18(1, c) [ 0 >= m ] (?, 1) f32(a, c) -> f32(a, c) [ -a + 1 >= 0 /\ a >= 0 ] (2, 1) f18(a, c) -> f24(0, l) [ -a + 1 >= 0 /\ a - 1 >= 0 /\ a >= 1 ] (2, 1) f24(a, c) -> f32(1, c) [ -a >= 0 /\ a >= 0 /\ 0 >= a /\ l >= c + 1000 ] (2, 1) f24(a, c) -> f32(a, c) [ -a >= 0 /\ a >= 0 /\ 0 >= a /\ c + 999 >= l ] start location: f0 leaf cost: 1 By chaining the transition f0(a, c) -> f32(1, c) [ 0 >= m /\ n >= 1 ] with all transitions in problem 6, the following new transition is obtained: f0(a, c) -> f32(1, c) [ 0 >= m /\ n >= 1 /\ 0 >= 0 /\ 1 >= 0 ] We thus obtain the following problem: 7: T: (1, 2) f0(a, c) -> f32(1, c) [ 0 >= m /\ n >= 1 /\ 0 >= 0 /\ 1 >= 0 ] (1, 1) f0(a, c) -> f18(1, c) [ m >= 1 /\ n >= 1 ] (1, 1) f0(a, c) -> f18(1, c) [ 0 >= m ] (?, 1) f32(a, c) -> f32(a, c) [ -a + 1 >= 0 /\ a >= 0 ] (2, 1) f18(a, c) -> f24(0, l) [ -a + 1 >= 0 /\ a - 1 >= 0 /\ a >= 1 ] (2, 1) f24(a, c) -> f32(1, c) [ -a >= 0 /\ a >= 0 /\ 0 >= a /\ l >= c + 1000 ] (2, 1) f24(a, c) -> f32(a, c) [ -a >= 0 /\ a >= 0 /\ 0 >= a /\ c + 999 >= l ] start location: f0 leaf cost: 1 Complexity upper bound ? Time: 0.348 sec (SMT: 0.328 sec)