/export/starexec/sandbox2/solver/bin/starexec_run_Itrs /export/starexec/sandbox2/benchmark/theBenchmark.itrs /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE DP problem for innermost termination. P = cond2#(false, x, y) -> ack#(x - 1, ack(x, y - 1)) cond2#(false, x, y) -> ack#(x, y - 1) cond2#(true, I0, I1) -> ack#(I0 - 1, I1 + 1) cond1#(false, I2, I3) -> cond2#(I3 = 0, I2, I3) ackNat#(true, I8, I9) -> cond1#(I8 = 0, I8, I9) ack#(I10, I11) -> ackNat#(I10 >= 0 && I11 >= 0, I10, I11) f#(true, I12) -> f#(ack(10, 10) >= I12, I12 + 1) f#(true, I12) -> ack#(10, 10) R = cond2(false, x, y) -> ack(x - 1, ack(x, y - 1)) cond2(true, I0, I1) -> ack(I0 - 1, I1 + 1) cond1(false, I2, I3) -> cond2(I3 = 0, I2, I3) cond1(true, I4, I5) -> I5 + 1 ackNat(false, I6, I7) -> 0 ackNat(true, I8, I9) -> cond1(I8 = 0, I8, I9) ack(I10, I11) -> ackNat(I10 >= 0 && I11 >= 0, I10, I11) f(true, I12) -> f(ack(10, 10) >= I12, I12 + 1) This problem is converted using chaining, where edges between chained DPs are removed. DP problem for innermost termination. P = cond2#(false, x, y) -> ack#(x - 1, ack(x, y - 1)) cond2#(false, x, y) -> ack#(x, y - 1) cond2#(true, I0, I1) -> ack#(I0 - 1, I1 + 1) cond1#(false, I2, I3) -> cond2#(I3 = 0, I2, I3) ackNat#(true, I8, I9) -> cond1#(I8 = 0, I8, I9) ack#(I10, I11) -> ackNat#(I10 >= 0 && I11 >= 0, I10, I11) f#(true, I12) -> f_1#(I12) f#(true, I12) -> ack#(10, 10) f_1#(I12) -> f#(ack(10, 10) >= I12, I12 + 1) ack#(I10, I11) -> cond1#(I10 = 0, I10, I11) [I10 >= 0 && I11 >= 0] ack#(I10, I11) -> cond2#(I11 = 0, I10, I11) [I10 >= 0 && I11 >= 0, not(I10 = 0)] ack#(I10, I11) -> ack#(I10 - 1, I11 + 1) [I10 >= 0 && I11 >= 0, not(I10 = 0), I11 = 0] ack#(I10, I11) -> ack#(I10, I11 - 1) [I10 >= 0 && I11 >= 0, not(I10 = 0), not(I11 = 0)] ack#(I10, I11) -> ack#(I10 - 1, ack(I10, I11 - 1)) [I10 >= 0 && I11 >= 0, not(I10 = 0), not(I11 = 0)] ackNat#(true, I8, I9) -> cond2#(I9 = 0, I8, I9) [not(I8 = 0)] ackNat#(true, I8, I9) -> ack#(I8 - 1, I9 + 1) [not(I8 = 0), I9 = 0] ackNat#(true, I8, I9) -> ack#(I8, I9 - 1) [not(I8 = 0), not(I9 = 0)] ackNat#(true, I8, I9) -> ack#(I8 - 1, ack(I8, I9 - 1)) [not(I8 = 0), not(I9 = 0)] cond1#(false, I2, I3) -> ack#(I2 - 1, ack(I2, I3 - 1)) [not(I3 = 0)] cond1#(false, I2, I3) -> ack#(I2, I3 - 1) [not(I3 = 0)] cond1#(false, I2, I3) -> ack#(I2 - 1, I3 + 1) [I3 = 0] R = cond2(false, x, y) -> ack(x - 1, ack(x, y - 1)) cond2(true, I0, I1) -> ack(I0 - 1, I1 + 1) cond1(false, I2, I3) -> cond2(I3 = 0, I2, I3) cond1(true, I4, I5) -> I5 + 1 ackNat(false, I6, I7) -> 0 ackNat(true, I8, I9) -> cond1(I8 = 0, I8, I9) ack(I10, I11) -> ackNat(I10 >= 0 && I11 >= 0, I10, I11) f(true, I12) -> f(ack(10, 10) >= I12, I12 + 1) The dependency graph for this problem is: 0 -> 13, 12, 11, 10, 9, 5 1 -> 13, 12, 11, 10, 9, 5 2 -> 13, 12, 11, 10, 9, 5 3 -> 4 -> 5 -> 6 -> 8 7 -> 13, 12, 10, 9, 5 8 -> 7, 6 9 -> 10 -> 11 -> 13, 12, 5, 9, 10 12 -> 13, 12, 5, 9, 10, 11 13 -> 13, 5, 9, 10, 11, 12 14 -> 15 -> 5, 9, 10, 12, 13 16 -> 5, 9, 10, 11, 12, 13 17 -> 5, 9, 10, 11, 12, 13 18 -> 5, 9, 10, 11, 12, 13 19 -> 5, 9, 10, 11, 12, 13 20 -> 5, 9, 10, 12, 13 Where: 0) cond2#(false, x, y) -> ack#(x - 1, ack(x, y - 1)) 1) cond2#(false, x, y) -> ack#(x, y - 1) 2) cond2#(true, I0, I1) -> ack#(I0 - 1, I1 + 1) 3) cond1#(false, I2, I3) -> cond2#(I3 = 0, I2, I3) 4) ackNat#(true, I8, I9) -> cond1#(I8 = 0, I8, I9) 5) ack#(I10, I11) -> ackNat#(I10 >= 0 && I11 >= 0, I10, I11) 6) f#(true, I12) -> f_1#(I12) 7) f#(true, I12) -> ack#(10, 10) 8) f_1#(I12) -> f#(ack(10, 10) >= I12, I12 + 1) 9) ack#(I10, I11) -> cond1#(I10 = 0, I10, I11) [I10 >= 0 && I11 >= 0] 10) ack#(I10, I11) -> cond2#(I11 = 0, I10, I11) [I10 >= 0 && I11 >= 0, not(I10 = 0)] 11) ack#(I10, I11) -> ack#(I10 - 1, I11 + 1) [I10 >= 0 && I11 >= 0, not(I10 = 0), I11 = 0] 12) ack#(I10, I11) -> ack#(I10, I11 - 1) [I10 >= 0 && I11 >= 0, not(I10 = 0), not(I11 = 0)] 13) ack#(I10, I11) -> ack#(I10 - 1, ack(I10, I11 - 1)) [I10 >= 0 && I11 >= 0, not(I10 = 0), not(I11 = 0)] 14) ackNat#(true, I8, I9) -> cond2#(I9 = 0, I8, I9) [not(I8 = 0)] 15) ackNat#(true, I8, I9) -> ack#(I8 - 1, I9 + 1) [not(I8 = 0), I9 = 0] 16) ackNat#(true, I8, I9) -> ack#(I8, I9 - 1) [not(I8 = 0), not(I9 = 0)] 17) ackNat#(true, I8, I9) -> ack#(I8 - 1, ack(I8, I9 - 1)) [not(I8 = 0), not(I9 = 0)] 18) cond1#(false, I2, I3) -> ack#(I2 - 1, ack(I2, I3 - 1)) [not(I3 = 0)] 19) cond1#(false, I2, I3) -> ack#(I2, I3 - 1) [not(I3 = 0)] 20) cond1#(false, I2, I3) -> ack#(I2 - 1, I3 + 1) [I3 = 0] We have the following SCCs. { 6, 8 } { 11, 12, 13 } DP problem for innermost termination. P = ack#(I10, I11) -> ack#(I10 - 1, I11 + 1) [I10 >= 0 && I11 >= 0, not(I10 = 0), I11 = 0] ack#(I10, I11) -> ack#(I10, I11 - 1) [I10 >= 0 && I11 >= 0, not(I10 = 0), not(I11 = 0)] ack#(I10, I11) -> ack#(I10 - 1, ack(I10, I11 - 1)) [I10 >= 0 && I11 >= 0, not(I10 = 0), not(I11 = 0)] R = cond2(false, x, y) -> ack(x - 1, ack(x, y - 1)) cond2(true, I0, I1) -> ack(I0 - 1, I1 + 1) cond1(false, I2, I3) -> cond2(I3 = 0, I2, I3) cond1(true, I4, I5) -> I5 + 1 ackNat(false, I6, I7) -> 0 ackNat(true, I8, I9) -> cond1(I8 = 0, I8, I9) ack(I10, I11) -> ackNat(I10 >= 0 && I11 >= 0, I10, I11) f(true, I12) -> f(ack(10, 10) >= I12, I12 + 1) We use the reverse value criterion with the projection function NU: NU[ack#(z1,z2)] = z1 This gives the following inequalities: I10 >= 0 && I11 >= 0/\not(I10 = 0)/\I11 = 0 ==> I10 > I10 - 1 with I10 >= 0 I10 >= 0 && I11 >= 0/\not(I10 = 0)/\not(I11 = 0) ==> I10 >= I10 I10 >= 0 && I11 >= 0/\not(I10 = 0)/\not(I11 = 0) ==> I10 > I10 - 1 with I10 >= 0 We remove all the strictly oriented dependency pairs. DP problem for innermost termination. P = ack#(I10, I11) -> ack#(I10, I11 - 1) [I10 >= 0 && I11 >= 0, not(I10 = 0), not(I11 = 0)] R = cond2(false, x, y) -> ack(x - 1, ack(x, y - 1)) cond2(true, I0, I1) -> ack(I0 - 1, I1 + 1) cond1(false, I2, I3) -> cond2(I3 = 0, I2, I3) cond1(true, I4, I5) -> I5 + 1 ackNat(false, I6, I7) -> 0 ackNat(true, I8, I9) -> cond1(I8 = 0, I8, I9) ack(I10, I11) -> ackNat(I10 >= 0 && I11 >= 0, I10, I11) f(true, I12) -> f(ack(10, 10) >= I12, I12 + 1) We use the reverse value criterion with the projection function NU: NU[ack#(z1,z2)] = z2 This gives the following inequalities: I10 >= 0 && I11 >= 0/\not(I10 = 0)/\not(I11 = 0) ==> I11 > I11 - 1 with I11 >= 0 All dependency pairs are strictly oriented, so the entire dependency pair problem may be removed. DP problem for innermost termination. P = f#(true, I12) -> f_1#(I12) f_1#(I12) -> f#(ack(10, 10) >= I12, I12 + 1) R = cond2(false, x, y) -> ack(x - 1, ack(x, y - 1)) cond2(true, I0, I1) -> ack(I0 - 1, I1 + 1) cond1(false, I2, I3) -> cond2(I3 = 0, I2, I3) cond1(true, I4, I5) -> I5 + 1 ackNat(false, I6, I7) -> 0 ackNat(true, I8, I9) -> cond1(I8 = 0, I8, I9) ack(I10, I11) -> ackNat(I10 >= 0 && I11 >= 0, I10, I11) f(true, I12) -> f(ack(10, 10) >= I12, I12 + 1)