7.56/2.81 NO 7.56/2.82 proof of /export/starexec/sandbox/benchmark/theBenchmark.jar 7.56/2.82 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.56/2.82 7.56/2.82 7.56/2.82 termination of the given Bare JBC problem could be disproven: 7.56/2.82 7.56/2.82 (0) Bare JBC problem 7.56/2.82 (1) BareJBCToJBCProof [EQUIVALENT, 95 ms] 7.56/2.82 (2) JBC problem 7.56/2.82 (3) JBCToGraph [EQUIVALENT, 309 ms] 7.56/2.82 (4) JBCTerminationGraph 7.56/2.82 (5) JBCNonTerm [COMPLETE, 277 ms] 7.56/2.82 (6) NO 7.56/2.82 7.56/2.82 7.56/2.82 ---------------------------------------- 7.56/2.82 7.56/2.82 (0) 7.56/2.82 Obligation: 7.56/2.82 need to prove termination of the following program: 7.56/2.82 package simple.ex08; 7.56/2.82 7.56/2.82 public class Ex08 { 7.56/2.82 7.56/2.82 public static void loop(int i) { 7.56/2.82 boolean up = false; 7.56/2.82 while (i > 0) { 7.56/2.82 if (i == 1) { 7.56/2.82 up = true; 7.56/2.82 } 7.56/2.82 if (i == 10) { 7.56/2.82 up = false; 7.56/2.82 } 7.56/2.82 if (up) { 7.56/2.82 i++; 7.56/2.82 } else { 7.56/2.82 i--; 7.56/2.82 } 7.56/2.82 } 7.56/2.82 } 7.56/2.82 } 7.56/2.82 7.56/2.82 7.56/2.82 package simple.ex08; 7.56/2.82 7.56/2.82 public class Main { 7.56/2.82 7.56/2.82 /** 7.56/2.82 * @param args 7.56/2.82 */ 7.56/2.82 public static void main(String[] args) { 7.56/2.82 Ex08.loop(args.length); 7.56/2.82 } 7.56/2.82 7.56/2.82 } 7.56/2.82 7.56/2.82 7.56/2.82 7.56/2.82 ---------------------------------------- 7.56/2.82 7.56/2.82 (1) BareJBCToJBCProof (EQUIVALENT) 7.56/2.82 initialized classpath 7.56/2.82 ---------------------------------------- 7.56/2.82 7.56/2.82 (2) 7.56/2.82 Obligation: 7.56/2.82 need to prove termination of the following program: 7.56/2.82 package simple.ex08; 7.56/2.82 7.56/2.82 public class Ex08 { 7.56/2.82 7.56/2.82 public static void loop(int i) { 7.56/2.82 boolean up = false; 7.56/2.82 while (i > 0) { 7.56/2.82 if (i == 1) { 7.56/2.82 up = true; 7.56/2.82 } 7.56/2.82 if (i == 10) { 7.56/2.82 up = false; 7.56/2.82 } 7.56/2.82 if (up) { 7.56/2.82 i++; 7.56/2.82 } else { 7.56/2.82 i--; 7.56/2.82 } 7.56/2.82 } 7.56/2.82 } 7.56/2.82 } 7.56/2.82 7.56/2.82 7.56/2.82 package simple.ex08; 7.56/2.82 7.56/2.82 public class Main { 7.56/2.82 7.56/2.82 /** 7.56/2.82 * @param args 7.56/2.82 */ 7.56/2.82 public static void main(String[] args) { 7.56/2.82 Ex08.loop(args.length); 7.56/2.82 } 7.56/2.82 7.56/2.82 } 7.56/2.82 7.56/2.82 7.56/2.82 7.56/2.82 ---------------------------------------- 7.56/2.82 7.56/2.82 (3) JBCToGraph (EQUIVALENT) 7.56/2.82 Constructed TerminationGraph. 7.56/2.82 ---------------------------------------- 7.56/2.82 7.56/2.82 (4) 7.56/2.82 Obligation: 7.56/2.82 Termination Graph based on JBC Program: 7.56/2.82 simple.ex08.Main.main([Ljava/lang/String;)V: Graph of 57 nodes with 1 SCC. 7.56/2.82 7.56/2.82 7.56/2.82 7.56/2.82 7.56/2.82 7.56/2.82 ---------------------------------------- 7.56/2.82 7.56/2.82 (5) JBCNonTerm (COMPLETE) 7.56/2.82 Reached a loop using the following run: 7.56/2.82 7.56/2.82 0: 7.56/2.82 a32([java.lang.String...]): length 1 -->{java.lang.Object...} 7.56/2.82 YES: (JL1) 7.56/2.82 1: 7.56/2.82 a32([java.lang.String...]): length 1 -->{java.lang.Object...} 7.56/2.82 YES: (JL1) 7.56/2.82 2: 7.56/2.82 YES: (JL1) 7.56/2.82 3: 7.56/2.82 7.56/2.82 YES: (JL1) 7.56/2.82 4: 7.56/2.82 7.56/2.82 YES: (JL1) 7.56/2.82 5: 7.56/2.82 7.56/2.82 YES: (JL1) 7.56/2.82 Start state of loop: 7.56/2.82 7.56/2.82 7.56/2.82 [a12(lv_0_0)] 7.56/2.82 7.56/2.82 i80: # 7.56/2.82 i81: [0,1](2,1) 7.56/2.82 i49: [0,+inf)(l2) 7.56/2.82 a12([java.lang.String...]): length i49 -->{java.lang.Object...} 7.56/2.82 YES: (JL1) 7.56/2.82 7.56/2.82 7.56/2.82 In the loop head node, references [i80, i81] were interesting. 7.56/2.82 7.56/2.82 All methods calls in the loop body are side-effect free, hence they can be ignored. 7.56/2.82 7.56/2.82 By SMT, we could prove 7.56/2.82 7.56/2.82 ((0 <= initial_i81 and initial_i81 <= 1 and 0 <= initial_i49) and ((((path1_i80 = path1_i86 and 2 = res_i80 and 1 = res_i81 and path1_i80 = initial_i80 and path1_i81 = initial_i81) and (path1_i86 > 0 and path1_i86 = 1 and path1_i86 = 1 and 1 = 1 and 1 > 0)) or ((path2_i80 = path2_i86 and path2_i86 = path2_i87 and path2_i87 = path2_i88 and path2_i88 = path2_i90 and path2_i93 = (path2_i90 + 1) and path2_i93 = res_i80 and 1 = res_i81 and path2_i80 = initial_i80 and path2_i81 = initial_i81) and (path2_i86 > 0 and T and 1 = 1 and path2_i87 > 1 and T and 10 = 10 and path2_i88 < 10 and path2_i81 = 1 and 1 > 0)) or ((path3_i80 = path3_i86 and path3_i86 = path3_i87 and path3_i87 = path3_i88 and path3_i88 = path3_i90 and path3_i94 = (path3_i90 + -1) and path3_i94 = res_i80 and 0 = res_i81 and path3_i80 = initial_i80 and path3_i81 = initial_i81) and (path3_i86 > 0 and T and 1 = 1 and path3_i87 > 1 and T and 10 = 10 and path3_i88 < 10 and path3_i81 = 0 and T)) or ((path4_i80 = path4_i86 and path4_i86 = path4_i87 and 9 = res_i80 and 0 = res_i81 and path4_i80 = initial_i80 and path4_i81 = initial_i81) and (path4_i86 > 0 and T and 1 = 1 and path4_i87 > 1 and path4_i87 = 10 and path4_i87 = 10 and 10 = 10 and T)) or ((path5_i80 = path5_i86 and path5_i86 = path5_i87 and path5_i87 = path5_i89 and path5_i89 = path5_i90 and path5_i93 = (path5_i90 + 1) and path5_i93 = res_i80 and 1 = res_i81 and path5_i80 = initial_i80 and path5_i81 = initial_i81) and (path5_i86 > 0 and T and 1 = 1 and path5_i87 > 1 and T and 10 = 10 and path5_i89 > 10 and path5_i81 = 1 and 1 > 0)) or ((path6_i80 = path6_i86 and path6_i86 = path6_i87 and path6_i87 = path6_i89 and path6_i89 = path6_i90 and path6_i94 = (path6_i90 + -1) and path6_i94 = res_i80 and 0 = res_i81 and path6_i80 = initial_i80 and path6_i81 = initial_i81) and (path6_i86 > 0 and T and 1 = 1 and path6_i87 > 1 and T and 10 = 10 and path6_i89 > 10 and path6_i81 = 0 and T))) and (((res1_i80 = res1_i86 and res_i80 = res1_i80 and res_i81 = res1_i81) and !(res1_i86 > 0 and res1_i86 = 1 and res1_i86 = 1 and 1 = 1 and 1 > 0)) and ((res2_i80 = res2_i86 and res2_i86 = res2_i87 and res2_i87 = res2_i88 and res2_i88 = res2_i90 and res2_i93 = (res2_i90 + 1) and res_i80 = res2_i80 and res_i81 = res2_i81) and !(res2_i86 > 0 and T and 1 = 1 and res2_i87 > 1 and T and 10 = 10 and res2_i88 < 10 and res2_i81 = 1 and 1 > 0)) and ((res3_i80 = res3_i86 and res3_i86 = res3_i87 and res3_i87 = res3_i88 and res3_i88 = res3_i90 and res3_i94 = (res3_i90 + -1) and res_i80 = res3_i80 and res_i81 = res3_i81) and !(res3_i86 > 0 and T and 1 = 1 and res3_i87 > 1 and T and 10 = 10 and res3_i88 < 10 and res3_i81 = 0 and T)) and ((res4_i80 = res4_i86 and res4_i86 = res4_i87 and res_i80 = res4_i80 and res_i81 = res4_i81) and !(res4_i86 > 0 and T and 1 = 1 and res4_i87 > 1 and res4_i87 = 10 and res4_i87 = 10 and 10 = 10 and T)) and ((res5_i80 = res5_i86 and res5_i86 = res5_i87 and res5_i87 = res5_i89 and res5_i89 = res5_i90 and res5_i93 = (res5_i90 + 1) and res_i80 = res5_i80 and res_i81 = res5_i81) and !(res5_i86 > 0 and T and 1 = 1 and res5_i87 > 1 and T and 10 = 10 and res5_i89 > 10 and res5_i81 = 1 and 1 > 0)) and ((res6_i80 = res6_i86 and res6_i86 = res6_i87 and res6_i87 = res6_i89 and res6_i89 = res6_i90 and res6_i94 = (res6_i90 + -1) and res_i80 = res6_i80 and res_i81 = res6_i81) and !(res6_i86 > 0 and T and 1 = 1 and res6_i87 > 1 and T and 10 = 10 and res6_i89 > 10 and res6_i81 = 0 and T))))) 7.56/2.82 7.56/2.82 to be UNSAT. Consequently, the loop will not terminate. 7.56/2.82 ---------------------------------------- 7.56/2.82 7.56/2.82 (6) 7.56/2.82 NO 7.56/2.84 EOF