7.09/2.85 NO 7.09/2.87 proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar 7.09/2.87 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.09/2.87 7.09/2.87 7.09/2.87 termination of the given Bare JBC problem could be disproven: 7.09/2.87 7.09/2.87 (0) Bare JBC problem 7.09/2.87 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 7.09/2.87 (2) JBC problem 7.09/2.87 (3) JBCToGraph [EQUIVALENT, 357 ms] 7.09/2.87 (4) JBCTerminationGraph 7.09/2.87 (5) JBCNonTerm [COMPLETE, 329 ms] 7.09/2.87 (6) NO 7.09/2.87 7.09/2.87 7.09/2.87 ---------------------------------------- 7.09/2.87 7.09/2.87 (0) 7.09/2.87 Obligation: 7.09/2.87 need to prove termination of the following program: 7.09/2.87 package simple.narrowKonv; 7.09/2.87 7.09/2.87 public class Main { 7.09/2.87 7.09/2.87 /** 7.09/2.87 * @param args 7.09/2.87 */ 7.09/2.87 public static void main(String[] args) { 7.09/2.87 7.09/2.87 NarrowKonv.loop(args.length); 7.09/2.87 } 7.09/2.87 7.09/2.87 } 7.09/2.87 7.09/2.87 7.09/2.87 package simple.narrowKonv; 7.09/2.87 7.09/2.87 public class NarrowKonv { 7.09/2.87 7.09/2.87 public static void loop(int i) { 7.09/2.87 int range = 20; 7.09/2.87 while (0 <= i && i <= range) { 7.09/2.87 if (!(0 == i && i == range)) { 7.09/2.87 if (i == range) { 7.09/2.87 i = 0; 7.09/2.87 range--; 7.09/2.87 } else { 7.09/2.87 i++; 7.09/2.87 } 7.09/2.87 } 7.09/2.87 } 7.09/2.87 } 7.09/2.87 } 7.09/2.87 7.09/2.87 7.09/2.87 7.09/2.87 ---------------------------------------- 7.09/2.87 7.09/2.87 (1) BareJBCToJBCProof (EQUIVALENT) 7.09/2.87 initialized classpath 7.09/2.87 ---------------------------------------- 7.09/2.87 7.09/2.87 (2) 7.09/2.87 Obligation: 7.09/2.87 need to prove termination of the following program: 7.09/2.87 package simple.narrowKonv; 7.09/2.87 7.09/2.87 public class Main { 7.09/2.87 7.09/2.87 /** 7.09/2.87 * @param args 7.09/2.87 */ 7.09/2.87 public static void main(String[] args) { 7.09/2.87 7.09/2.87 NarrowKonv.loop(args.length); 7.09/2.87 } 7.09/2.87 7.09/2.87 } 7.09/2.87 7.09/2.87 7.09/2.87 package simple.narrowKonv; 7.09/2.87 7.09/2.87 public class NarrowKonv { 7.09/2.87 7.09/2.87 public static void loop(int i) { 7.09/2.87 int range = 20; 7.09/2.87 while (0 <= i && i <= range) { 7.09/2.87 if (!(0 == i && i == range)) { 7.09/2.87 if (i == range) { 7.09/2.87 i = 0; 7.09/2.87 range--; 7.09/2.87 } else { 7.09/2.87 i++; 7.09/2.87 } 7.09/2.87 } 7.09/2.87 } 7.09/2.87 } 7.09/2.87 } 7.09/2.87 7.09/2.87 7.09/2.87 7.09/2.87 ---------------------------------------- 7.09/2.87 7.09/2.87 (3) JBCToGraph (EQUIVALENT) 7.09/2.87 Constructed TerminationGraph. 7.09/2.87 ---------------------------------------- 7.09/2.87 7.09/2.87 (4) 7.09/2.87 Obligation: 7.09/2.87 Termination Graph based on JBC Program: 7.09/2.87 simple.narrowKonv.Main.main([Ljava/lang/String;)V: Graph of 51 nodes with 1 SCC. 7.09/2.87 7.09/2.87 7.09/2.87 7.09/2.87 7.09/2.87 7.09/2.87 ---------------------------------------- 7.09/2.87 7.09/2.87 (5) JBCNonTerm (COMPLETE) 7.09/2.87 Reached a loop using the following run: 7.09/2.87 7.09/2.87 0: 7.09/2.87 a140([java.lang.String...]): length 1 -->{java.lang.Object...} 7.09/2.87 YES: (JL1) 7.09/2.87 1: 7.09/2.87 a140([java.lang.String...]): length 1 -->{java.lang.Object...} 7.09/2.87 YES: (JL1) 7.09/2.87 2: 7.09/2.87 YES: (JL1) 7.09/2.87 3: 7.09/2.87 7.09/2.87 YES: (JL1) 7.09/2.87 4: 7.09/2.87 7.09/2.87 YES: (JL1) 7.09/2.87 5: 7.09/2.87 7.09/2.87 YES: (JL1) 7.09/2.87 Start state of loop: 7.09/2.87 7.09/2.87 7.09/2.87 [a14(lv_0_0)] 7.09/2.87 7.09/2.87 i66: [0,+inf)(l1) 7.09/2.87 i67: # 7.09/2.87 i43: [0,+inf)(l1) 7.09/2.87 a14([java.lang.String...]): length i43 -->{java.lang.Object...} 7.09/2.87 YES: (JL1) 7.09/2.87 7.09/2.87 7.09/2.87 In the loop head node, references [i66, i67] were interesting. 7.09/2.87 7.09/2.87 All methods calls in the loop body are side-effect free, hence they can be ignored. 7.09/2.87 7.09/2.87 By SMT, we could prove 7.09/2.87 7.09/2.87 ((0 <= initial_i66 and 0 <= initial_i43) and ((((0 = res_i66 and 0 = res_i67 and path1_i66 = initial_i66 and path1_i67 = initial_i67) and (0 <= path1_i66 and path1_i66 <= path1_i67 and path1_i66 <= path1_i67 and T and path1_i66 = 0 and T and path1_i67 = 0)) or ((path2_i67 = path2_i72 and path2_i66 = path2_i71 and path2_i76 = (path2_i71 + 1) and path2_i76 = res_i66 and path2_i72 = res_i67 and path2_i66 = initial_i66 and path2_i67 = initial_i67) and (0 <= path2_i66 and path2_i66 <= path2_i67 and path2_i66 <= path2_i67 and T and 0 = 0 and 0 < path2_i71 and path2_i71 != path2_i72 and path2_i71 < path2_i72)) or ((path3_i67 = path3_i72 and path3_i66 = path3_i71 and path3_i79 = (path3_i72 + -1) and 0 = res_i66 and path3_i79 = res_i67 and path3_i66 = initial_i66 and path3_i67 = initial_i67) and (0 <= path3_i66 and path3_i66 <= path3_i67 and path3_i66 <= path3_i67 and T and 0 = 0 and 0 < path3_i71 and path3_i71 = path3_i72 and path3_i72 = path3_i72)) or ((path4_i67 = path4_i73 and 1 = res_i66 and path4_i73 = res_i67 and path4_i66 = initial_i66 and path4_i67 = initial_i67) and (0 <= path4_i66 and path4_i66 <= path4_i67 and path4_i66 <= path4_i67 and T and path4_i66 = 0 and T and 0 = 0 and 0 < path4_i73 and 0 < path4_i73)) or ((path2_i67 = path2_i72 and path2_i66 = path2_i71 and path2_i76 = (path2_i71 + 1) and path2_i76 = res_i66 and path2_i72 = res_i67 and path2_i66 = initial_i66 and path2_i67 = initial_i67) and (0 <= path2_i66 and path2_i66 <= path2_i67 and path2_i66 <= path2_i67 and T and 0 = 0 and 0 < path2_i71 and path2_i71 < path2_i72 and path2_i71 < path2_i72)) or ((path2_i67 = path2_i72 and path2_i66 = path2_i71 and path2_i76 = (path2_i71 + 1) and path2_i76 = res_i66 and path2_i72 = res_i67 and path2_i66 = initial_i66 and path2_i67 = initial_i67) and (0 <= path2_i66 and path2_i66 <= path2_i67 and path2_i66 <= path2_i67 and T and 0 = 0 and 0 < path2_i71 and path2_i71 < path2_i72 and path2_i71 > path2_i72))) and (((res_i66 = res1_i66 and res_i67 = res1_i67) and !(0 <= res1_i66 and res1_i66 <= res1_i67 and res1_i66 <= res1_i67 and T and res1_i66 = 0 and T and res1_i67 = 0)) and ((res2_i67 = res2_i72 and res2_i66 = res2_i71 and res2_i76 = (res2_i71 + 1) and res_i66 = res2_i66 and res_i67 = res2_i67) and !(0 <= res2_i66 and res2_i66 <= res2_i67 and res2_i66 <= res2_i67 and T and 0 = 0 and 0 < res2_i71 and res2_i71 != res2_i72 and res2_i71 < res2_i72)) and ((res3_i67 = res3_i72 and res3_i66 = res3_i71 and res3_i79 = (res3_i72 + -1) and res_i66 = res3_i66 and res_i67 = res3_i67) and !(0 <= res3_i66 and res3_i66 <= res3_i67 and res3_i66 <= res3_i67 and T and 0 = 0 and 0 < res3_i71 and res3_i71 = res3_i72 and res3_i72 = res3_i72)) and ((res4_i67 = res4_i73 and res_i66 = res4_i66 and res_i67 = res4_i67) and !(0 <= res4_i66 and res4_i66 <= res4_i67 and res4_i66 <= res4_i67 and T and res4_i66 = 0 and T and 0 = 0 and 0 < res4_i73 and 0 < res4_i73)) and ((res2_i67 = res2_i72 and res2_i66 = res2_i71 and res2_i76 = (res2_i71 + 1) and res_i66 = res2_i66 and res_i67 = res2_i67) and !(0 <= res2_i66 and res2_i66 <= res2_i67 and res2_i66 <= res2_i67 and T and 0 = 0 and 0 < res2_i71 and res2_i71 < res2_i72 and res2_i71 < res2_i72)) and ((res2_i67 = res2_i72 and res2_i66 = res2_i71 and res2_i76 = (res2_i71 + 1) and res_i66 = res2_i66 and res_i67 = res2_i67) and !(0 <= res2_i66 and res2_i66 <= res2_i67 and res2_i66 <= res2_i67 and T and 0 = 0 and 0 < res2_i71 and res2_i71 < res2_i72 and res2_i71 > res2_i72))))) 7.09/2.87 7.09/2.87 to be UNSAT. Consequently, the loop will not terminate. 7.09/2.87 ---------------------------------------- 7.09/2.87 7.09/2.87 (6) 7.09/2.87 NO 7.32/2.94 EOF