/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, 523 ms] (4) JBCTerminationGraph (5) JBCNonTerm [COMPLETE, 53 ms] (6) NO ---------------------------------------- (0) Obligation: need to prove termination of the following program: public class UpAndDown { public static void upAndDown(int i, boolean up) { if (0 <= i && i <= 10) { if (i == 10) up = false; if (i == 0) up = true; if (up) i++; else i--; upAndDown(i, up); } } public static void main(String[] args) { upAndDown(args.length, false); } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: public class UpAndDown { public static void upAndDown(int i, boolean up) { if (0 <= i && i <= 10) { if (i == 10) up = false; if (i == 0) up = true; if (up) i++; else i--; upAndDown(i, up); } } public static void main(String[] args) { upAndDown(args.length, false); } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: UpAndDown.main([Ljava/lang/String;)V: Graph of 15 nodes with 0 SCCs. UpAndDown.upAndDown(IZ)V: Graph of 75 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: [i39(lv_0_0), i40(lv_0_1)] i39: [0,+inf)(l1) i40: [0,1](1,1) i41: [0,1](1,1) YES: (JL1) In the loop head node, references [i39, i40, i41] 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_i39 and 0 <= initial_i40 and initial_i40 <= 1 and 0 <= initial_i41 and initial_i41 <= 1) and ((((path1_i39 = path1_i42 and path1_i42 = path1_i48 and path1_i48 = path1_i50 and path1_i53 = (path1_i50 + -1) and path1_i53 = res_i39 and 0 = res_i40 and 0 = res_i41 and path1_i39 = initial_i39 and path1_i40 = initial_i40 and path1_i41 = initial_i41) and (0 <= path1_i39 and T and 10 = 10 and path1_i42 <= 10 and T and 10 = 10 and path1_i48 < 10 and path1_i50 > 0 and path1_i41 = 0 and T)) or ((path2_i39 = path2_i42 and 9 = res_i39 and 0 = res_i40 and 0 = res_i41 and path2_i39 = initial_i39 and path2_i40 = initial_i40 and path2_i41 = initial_i41) and (0 <= path2_i39 and T and 10 = 10 and path2_i42 <= 10 and path2_i42 = 10 and path2_i42 = 10 and 10 = 10 and 10 > 0 and T)) or ((path3_i39 = path3_i42 and path3_i42 = path3_i48 and path3_i48 = path3_i50 and path3_i52 = (path3_i50 + 1) and path3_i52 = res_i39 and 1 = res_i40 and 1 = res_i41 and path3_i39 = initial_i39 and path3_i40 = initial_i40 and path3_i41 = initial_i41) and (0 <= path3_i39 and T and 10 = 10 and path3_i42 <= 10 and T and 10 = 10 and path3_i48 < 10 and path3_i50 > 0 and path3_i41 = 1 and 1 > 0)) or ((path4_i39 = path4_i42 and path4_i42 = path4_i48 and 1 = res_i39 and 1 = res_i40 and 1 = res_i41 and path4_i39 = initial_i39 and path4_i40 = initial_i40 and path4_i41 = initial_i41) and (0 <= path4_i39 and T and 10 = 10 and path4_i42 <= 10 and T and 10 = 10 and path4_i48 < 10 and path4_i48 = 0 and T and 1 > 0))) and (((res1_i39 = res1_i42 and res1_i42 = res1_i48 and res1_i48 = res1_i50 and res1_i53 = (res1_i50 + -1) and res_i39 = res1_i39 and res_i40 = res1_i40 and res_i41 = res1_i41) and !(0 <= res1_i39 and T and 10 = 10 and res1_i42 <= 10 and T and 10 = 10 and res1_i48 < 10 and res1_i50 > 0 and res1_i41 = 0 and T)) and ((res2_i39 = res2_i42 and res_i39 = res2_i39 and res_i40 = res2_i40 and res_i41 = res2_i41) and !(0 <= res2_i39 and T and 10 = 10 and res2_i42 <= 10 and res2_i42 = 10 and res2_i42 = 10 and 10 = 10 and 10 > 0 and T)) and ((res3_i39 = res3_i42 and res3_i42 = res3_i48 and res3_i48 = res3_i50 and res3_i52 = (res3_i50 + 1) and res_i39 = res3_i39 and res_i40 = res3_i40 and res_i41 = res3_i41) and !(0 <= res3_i39 and T and 10 = 10 and res3_i42 <= 10 and T and 10 = 10 and res3_i48 < 10 and res3_i50 > 0 and res3_i41 = 1 and 1 > 0)) and ((res4_i39 = res4_i42 and res4_i42 = res4_i48 and res_i39 = res4_i39 and res_i40 = res4_i40 and res_i41 = res4_i41) and !(0 <= res4_i39 and T and 10 = 10 and res4_i42 <= 10 and T and 10 = 10 and res4_i48 < 10 and res4_i48 = 0 and T and 1 > 0))))) to be UNSAT. Consequently, the loop will not terminate. ---------------------------------------- (6) NO