/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.jar /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox/benchmark/theBenchmark.jar # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty termination of the given Bare JBC problem could be disproven: (0) Bare JBC problem (1) BareJBCToJBCProof [EQUIVALENT, 97 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 418 ms] (4) JBCTerminationGraph (5) JBCNonTerm [COMPLETE, 62 ms] (6) NO ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class NarrowKonv { public static void loop(int i, int range) { if (0 <= i && i <= range) { if (!(0 == i && i == range)) { if (i == range) { i = 0; range--; } else i++; } loop(i, range); } } public static void main(String[] args) { loop(args.length, 20); } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: public class NarrowKonv { public static void loop(int i, int range) { if (0 <= i && i <= range) { if (!(0 == i && i == range)) { if (i == range) { i = 0; range--; } else i++; } loop(i, range); } } public static void main(String[] args) { loop(args.length, 20); } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: NarrowKonv.main([Ljava/lang/String;)V: Graph of 13 nodes with 0 SCCs. NarrowKonv.loop(II)V: Graph of 69 nodes with 0 SCCs. ---------------------------------------- (5) JBCNonTerm (COMPLETE) Reached a loop using the following run: 0: a2([java.lang.String...]): length 1 -->{java.lang.Object...} YES: (JL1) 1: a2([java.lang.String...]): length 1 -->{java.lang.Object...} YES: (JL1) 2: YES: (JL1) 3: YES: (JL1) 4: YES: (JL1) Start state of loop: [i122(lv_0_0), i123(lv_0_1)] i122: [0,+inf) i123: # i124: # YES: (JL1) In the loop head node, references [i122, i124, i123] were interesting. All methods calls in the loop body are side-effect free, hence they can be ignored. By SMT, we could prove (0 <= initial_i122 and ((((0 = res_i122 and 0 = res_i123 and 0 = res_i124 and path1_i122 = initial_i122 and path1_i123 = initial_i123 and path1_i124 = initial_i124) and (0 <= path1_i122 and path1_i122 <= path1_i124 and path1_i122 <= path1_i124 and T and path1_i122 = 0 and T and path1_i124 = 0)) or ((path2_i124 = path2_i132 and path2_i122 = path2_i131 and path2_i134 = (path2_i131 + 1) and path2_i134 = res_i122 and path2_i132 = res_i123 and path2_i132 = res_i124 and path2_i122 = initial_i122 and path2_i123 = initial_i123 and path2_i124 = initial_i124) and (0 <= path2_i122 and path2_i122 <= path2_i124 and path2_i122 <= path2_i124 and T and 0 = 0 and 0 < path2_i131 and path2_i131 != path2_i132 and path2_i131 < path2_i132)) or ((path3_i124 = path3_i132 and path3_i122 = path3_i131 and path3_i135 = (path3_i132 + -1) and 0 = res_i122 and path3_i135 = res_i123 and path3_i135 = res_i124 and path3_i122 = initial_i122 and path3_i123 = initial_i123 and path3_i124 = initial_i124) and (0 <= path3_i122 and path3_i122 <= path3_i124 and path3_i122 <= path3_i124 and T and 0 = 0 and 0 < path3_i131 and path3_i131 = path3_i132 and path3_i132 = path3_i132)) or ((path4_i124 = path4_i133 and 1 = res_i122 and path4_i133 = res_i123 and path4_i133 = res_i124 and path4_i122 = initial_i122 and path4_i123 = initial_i123 and path4_i124 = initial_i124) and (0 <= path4_i122 and path4_i122 <= path4_i124 and path4_i122 <= path4_i124 and T and path4_i122 = 0 and T and 0 = 0 and 0 < path4_i133 and 0 < path4_i133)) or ((path2_i124 = path2_i132 and path2_i122 = path2_i131 and path2_i134 = (path2_i131 + 1) and path2_i134 = res_i122 and path2_i132 = res_i123 and path2_i132 = res_i124 and path2_i122 = initial_i122 and path2_i123 = initial_i123 and path2_i124 = initial_i124) and (0 <= path2_i122 and path2_i122 <= path2_i124 and path2_i122 <= path2_i124 and T and 0 = 0 and 0 < path2_i131 and path2_i131 < path2_i132 and path2_i131 < path2_i132)) or ((path2_i124 = path2_i132 and path2_i122 = path2_i131 and path2_i134 = (path2_i131 + 1) and path2_i134 = res_i122 and path2_i132 = res_i123 and path2_i132 = res_i124 and path2_i122 = initial_i122 and path2_i123 = initial_i123 and path2_i124 = initial_i124) and (0 <= path2_i122 and path2_i122 <= path2_i124 and path2_i122 <= path2_i124 and T and 0 = 0 and 0 < path2_i131 and path2_i131 < path2_i132 and path2_i131 > path2_i132))) and (((res_i122 = res1_i122 and res_i123 = res1_i123 and res_i124 = res1_i124) and !(0 <= res1_i122 and res1_i122 <= res1_i124 and res1_i122 <= res1_i124 and T and res1_i122 = 0 and T and res1_i124 = 0)) and ((res2_i124 = res2_i132 and res2_i122 = res2_i131 and res2_i134 = (res2_i131 + 1) and res_i122 = res2_i122 and res_i123 = res2_i123 and res_i124 = res2_i124) and !(0 <= res2_i122 and res2_i122 <= res2_i124 and res2_i122 <= res2_i124 and T and 0 = 0 and 0 < res2_i131 and res2_i131 != res2_i132 and res2_i131 < res2_i132)) and ((res3_i124 = res3_i132 and res3_i122 = res3_i131 and res3_i135 = (res3_i132 + -1) and res_i122 = res3_i122 and res_i123 = res3_i123 and res_i124 = res3_i124) and !(0 <= res3_i122 and res3_i122 <= res3_i124 and res3_i122 <= res3_i124 and T and 0 = 0 and 0 < res3_i131 and res3_i131 = res3_i132 and res3_i132 = res3_i132)) and ((res4_i124 = res4_i133 and res_i122 = res4_i122 and res_i123 = res4_i123 and res_i124 = res4_i124) and !(0 <= res4_i122 and res4_i122 <= res4_i124 and res4_i122 <= res4_i124 and T and res4_i122 = 0 and T and 0 = 0 and 0 < res4_i133 and 0 < res4_i133)) and ((res2_i124 = res2_i132 and res2_i122 = res2_i131 and res2_i134 = (res2_i131 + 1) and res_i122 = res2_i122 and res_i123 = res2_i123 and res_i124 = res2_i124) and !(0 <= res2_i122 and res2_i122 <= res2_i124 and res2_i122 <= res2_i124 and T and 0 = 0 and 0 < res2_i131 and res2_i131 < res2_i132 and res2_i131 < res2_i132)) and ((res2_i124 = res2_i132 and res2_i122 = res2_i131 and res2_i134 = (res2_i131 + 1) and res_i122 = res2_i122 and res_i123 = res2_i123 and res_i124 = res2_i124) and !(0 <= res2_i122 and res2_i122 <= res2_i124 and res2_i122 <= res2_i124 and T and 0 = 0 and 0 < res2_i131 and res2_i131 < res2_i132 and res2_i131 > res2_i132))))) to be UNSAT. Consequently, the loop will not terminate. ---------------------------------------- (6) NO