/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.jar /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox2/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, 96 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 341 ms] (4) JBCTerminationGraph (5) JBCNonTerm [COMPLETE, 233 ms] (6) NO ---------------------------------------- (0) Obligation: need to prove termination of the following program: package simple.ex08; public class Ex08 { public static void loop(int i) { boolean up = false; while (i > 0) { if (i == 1) { up = true; } if (i == 10) { up = false; } if (up) { i++; } else { i--; } } } } package simple.ex08; public class Main { /** * @param args */ public static void main(String[] args) { Ex08.loop(args.length); } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: package simple.ex08; public class Ex08 { public static void loop(int i) { boolean up = false; while (i > 0) { if (i == 1) { up = true; } if (i == 10) { up = false; } if (up) { i++; } else { i--; } } } } package simple.ex08; public class Main { /** * @param args */ public static void main(String[] args) { Ex08.loop(args.length); } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: simple.ex08.Main.main([Ljava/lang/String;)V: Graph of 57 nodes with 1 SCC. ---------------------------------------- (5) JBCNonTerm (COMPLETE) Reached a loop using the following run: 0: a32([java.lang.String...]): length 1 -->{java.lang.Object...} YES: (JL1) 1: a32([java.lang.String...]): length 1 -->{java.lang.Object...} YES: (JL1) 2: YES: (JL1) 3: YES: (JL1) 4: YES: (JL1) 5: YES: (JL1) Start state of loop: [a12(lv_0_0)] i76: # i77: [0,1](2,1) i49: [0,+inf)(l2) a12([java.lang.String...]): length i49 -->{java.lang.Object...} YES: (JL1) In the loop head node, references [i76, i77] 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_i77 and initial_i77 <= 1 and 0 <= initial_i49) and ((((path1_i76 = path1_i82 and 2 = res_i76 and 1 = res_i77 and path1_i76 = initial_i76 and path1_i77 = initial_i77) and (path1_i82 > 0 and path1_i82 = 1 and path1_i82 = 1 and 1 = 1 and 1 > 0)) or ((path2_i76 = path2_i82 and path2_i82 = path2_i83 and path2_i83 = path2_i84 and path2_i84 = path2_i86 and path2_i89 = (path2_i86 + 1) and path2_i89 = res_i76 and 1 = res_i77 and path2_i76 = initial_i76 and path2_i77 = initial_i77) and (path2_i82 > 0 and T and 1 = 1 and path2_i83 > 1 and T and 10 = 10 and path2_i84 < 10 and path2_i77 = 1 and 1 > 0)) or ((path3_i76 = path3_i82 and path3_i82 = path3_i83 and path3_i83 = path3_i84 and path3_i84 = path3_i86 and path3_i90 = (path3_i86 + -1) and path3_i90 = res_i76 and 0 = res_i77 and path3_i76 = initial_i76 and path3_i77 = initial_i77) and (path3_i82 > 0 and T and 1 = 1 and path3_i83 > 1 and T and 10 = 10 and path3_i84 < 10 and path3_i77 = 0 and T)) or ((path4_i76 = path4_i82 and path4_i82 = path4_i83 and 9 = res_i76 and 0 = res_i77 and path4_i76 = initial_i76 and path4_i77 = initial_i77) and (path4_i82 > 0 and T and 1 = 1 and path4_i83 > 1 and path4_i83 = 10 and path4_i83 = 10 and 10 = 10 and T)) or ((path5_i76 = path5_i82 and path5_i82 = path5_i83 and path5_i83 = path5_i85 and path5_i85 = path5_i86 and path5_i89 = (path5_i86 + 1) and path5_i89 = res_i76 and 1 = res_i77 and path5_i76 = initial_i76 and path5_i77 = initial_i77) and (path5_i82 > 0 and T and 1 = 1 and path5_i83 > 1 and T and 10 = 10 and path5_i85 > 10 and path5_i77 = 1 and 1 > 0)) or ((path6_i76 = path6_i82 and path6_i82 = path6_i83 and path6_i83 = path6_i85 and path6_i85 = path6_i86 and path6_i90 = (path6_i86 + -1) and path6_i90 = res_i76 and 0 = res_i77 and path6_i76 = initial_i76 and path6_i77 = initial_i77) and (path6_i82 > 0 and T and 1 = 1 and path6_i83 > 1 and T and 10 = 10 and path6_i85 > 10 and path6_i77 = 0 and T))) and (((res1_i76 = res1_i82 and res_i76 = res1_i76 and res_i77 = res1_i77) and !(res1_i82 > 0 and res1_i82 = 1 and res1_i82 = 1 and 1 = 1 and 1 > 0)) and ((res2_i76 = res2_i82 and res2_i82 = res2_i83 and res2_i83 = res2_i84 and res2_i84 = res2_i86 and res2_i89 = (res2_i86 + 1) and res_i76 = res2_i76 and res_i77 = res2_i77) and !(res2_i82 > 0 and T and 1 = 1 and res2_i83 > 1 and T and 10 = 10 and res2_i84 < 10 and res2_i77 = 1 and 1 > 0)) and ((res3_i76 = res3_i82 and res3_i82 = res3_i83 and res3_i83 = res3_i84 and res3_i84 = res3_i86 and res3_i90 = (res3_i86 + -1) and res_i76 = res3_i76 and res_i77 = res3_i77) and !(res3_i82 > 0 and T and 1 = 1 and res3_i83 > 1 and T and 10 = 10 and res3_i84 < 10 and res3_i77 = 0 and T)) and ((res4_i76 = res4_i82 and res4_i82 = res4_i83 and res_i76 = res4_i76 and res_i77 = res4_i77) and !(res4_i82 > 0 and T and 1 = 1 and res4_i83 > 1 and res4_i83 = 10 and res4_i83 = 10 and 10 = 10 and T)) and ((res5_i76 = res5_i82 and res5_i82 = res5_i83 and res5_i83 = res5_i85 and res5_i85 = res5_i86 and res5_i89 = (res5_i86 + 1) and res_i76 = res5_i76 and res_i77 = res5_i77) and !(res5_i82 > 0 and T and 1 = 1 and res5_i83 > 1 and T and 10 = 10 and res5_i85 > 10 and res5_i77 = 1 and 1 > 0)) and ((res6_i76 = res6_i82 and res6_i82 = res6_i83 and res6_i83 = res6_i85 and res6_i85 = res6_i86 and res6_i90 = (res6_i86 + -1) and res_i76 = res6_i76 and res_i77 = res6_i77) and !(res6_i82 > 0 and T and 1 = 1 and res6_i83 > 1 and T and 10 = 10 and res6_i85 > 10 and res6_i77 = 0 and T))))) to be UNSAT. Consequently, the loop will not terminate. ---------------------------------------- (6) NO