31.50/9.74 NO 31.50/9.75 proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar 31.50/9.75 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 31.50/9.75 31.50/9.75 31.50/9.75 termination of the given Bare JBC problem could be disproven: 31.50/9.75 31.50/9.75 (0) Bare JBC problem 31.50/9.75 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 31.50/9.75 (2) JBC problem 31.50/9.75 (3) JBCToGraph [EQUIVALENT, 803 ms] 31.50/9.75 (4) JBCTerminationGraph 31.50/9.75 (5) JBCNonTerm [COMPLETE, 9165 ms] 31.50/9.75 (6) NO 31.50/9.75 31.50/9.75 31.50/9.75 ---------------------------------------- 31.50/9.75 31.50/9.75 (0) 31.50/9.75 Obligation: 31.50/9.75 need to prove termination of the following program: 31.50/9.75 package simple.narrowing; 31.50/9.75 31.50/9.75 public class Main { 31.50/9.75 31.50/9.75 /** 31.50/9.75 * @param args 31.50/9.75 */ 31.50/9.75 public static void main(String[] args) { 31.50/9.75 Narrowing.loop(args.length); 31.50/9.75 } 31.50/9.75 31.50/9.75 } 31.50/9.75 31.50/9.75 31.50/9.75 package simple.narrowing; 31.50/9.75 31.50/9.75 public class Narrowing { 31.50/9.75 31.50/9.75 public static void loop(int i) { 31.50/9.75 int range = 20; 31.50/9.75 boolean up = false; 31.50/9.75 while (0 <= i && i <= range) { 31.50/9.75 if (i == 0) { 31.50/9.75 up = true; 31.50/9.75 } 31.50/9.75 if (i == range) { 31.50/9.75 up = false; 31.50/9.75 } 31.50/9.75 if (up) { 31.50/9.75 i++; 31.50/9.75 } 31.50/9.75 if (!up) { 31.50/9.75 i--; 31.50/9.75 } 31.50/9.75 if (i == range-2) { 31.50/9.75 range--; 31.50/9.75 } 31.50/9.75 } 31.50/9.75 } 31.50/9.75 } 31.50/9.75 31.50/9.75 31.50/9.75 31.50/9.75 ---------------------------------------- 31.50/9.75 31.50/9.75 (1) BareJBCToJBCProof (EQUIVALENT) 31.50/9.75 initialized classpath 31.50/9.75 ---------------------------------------- 31.50/9.75 31.50/9.75 (2) 31.50/9.75 Obligation: 31.50/9.75 need to prove termination of the following program: 31.50/9.75 package simple.narrowing; 31.50/9.75 31.50/9.75 public class Main { 31.50/9.75 31.50/9.75 /** 31.50/9.75 * @param args 31.50/9.75 */ 31.50/9.75 public static void main(String[] args) { 31.50/9.75 Narrowing.loop(args.length); 31.50/9.75 } 31.50/9.75 31.50/9.75 } 31.50/9.75 31.50/9.75 31.50/9.75 package simple.narrowing; 31.50/9.75 31.50/9.75 public class Narrowing { 31.50/9.75 31.50/9.75 public static void loop(int i) { 31.50/9.75 int range = 20; 31.50/9.75 boolean up = false; 31.50/9.75 while (0 <= i && i <= range) { 31.50/9.75 if (i == 0) { 31.50/9.75 up = true; 31.50/9.75 } 31.50/9.75 if (i == range) { 31.50/9.75 up = false; 31.50/9.75 } 31.50/9.75 if (up) { 31.50/9.75 i++; 31.50/9.75 } 31.50/9.75 if (!up) { 31.50/9.75 i--; 31.50/9.75 } 31.50/9.75 if (i == range-2) { 31.50/9.75 range--; 31.50/9.75 } 31.50/9.75 } 31.50/9.75 } 31.50/9.75 } 31.50/9.75 31.50/9.75 31.50/9.75 31.50/9.75 ---------------------------------------- 31.50/9.75 31.50/9.75 (3) JBCToGraph (EQUIVALENT) 31.50/9.75 Constructed TerminationGraph. 31.50/9.75 ---------------------------------------- 31.50/9.75 31.50/9.75 (4) 31.50/9.75 Obligation: 31.50/9.75 Termination Graph based on JBC Program: 31.50/9.75 simple.narrowing.Main.main([Ljava/lang/String;)V: Graph of 117 nodes with 1 SCC. 31.50/9.75 31.50/9.75 31.50/9.75 31.50/9.75 31.50/9.75 31.50/9.75 ---------------------------------------- 31.50/9.75 31.50/9.75 (5) JBCNonTerm (COMPLETE) 31.50/9.75 Reached a loop using the following run: 31.50/9.75 31.50/9.75 0: 31.50/9.75 a238([java.lang.String...]): length 1 -->{java.lang.Object...} 31.50/9.75 YES: (JL1) 31.50/9.75 1: 31.50/9.75 a238([java.lang.String...]): length 1 -->{java.lang.Object...} 31.50/9.75 YES: (JL1) 31.50/9.75 2: 31.50/9.75 YES: (JL1) 31.50/9.75 3: 31.50/9.75 31.50/9.75 YES: (JL1) 31.50/9.75 4: 31.50/9.75 31.50/9.75 YES: (JL1) 31.50/9.75 5: 31.50/9.75 31.50/9.75 YES: (JL1) 31.50/9.75 6: 31.50/9.75 31.50/9.75 YES: (JL1) 31.50/9.75 7: 31.50/9.75 31.50/9.75 YES: (JL1) 31.50/9.75 Start state of loop: 31.50/9.75 31.50/9.75 31.50/9.75 [a66(lv_0_0)] 31.50/9.75 31.50/9.75 i358: # 31.50/9.75 i359: # 31.50/9.75 i360: # 31.50/9.75 i18: [0,+inf)(l1) 31.50/9.75 a66([java.lang.String...]): length i18 -->{java.lang.Object...} 31.50/9.75 YES: (JL1) 31.50/9.75 31.50/9.75 31.50/9.75 In the loop head node, references [i358, i359, i360] were interesting. 31.50/9.75 31.50/9.75 All methods calls in the loop body are side-effect free, hence they can be ignored. 31.50/9.75 31.50/9.75 By SMT, we could prove 31.50/9.75 31.50/9.75 (0 <= initial_i18 and ((((path1_i358 = path1_i368 and path1_i359 = path1_i371 and path1_i368 = path1_i370 and path1_i360 = path1_i375 and path1_i378 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i378 = res_i358 and path1_i371 = res_i359 and path1_i375 = res_i360 and path1_i358 = initial_i358 and path1_i359 = initial_i359 and path1_i360 = initial_i360) and (T and 0 = 0 and 0 <= path1_i368 and path1_i368 <= path1_i359 and path1_i368 <= path1_i359 and path1_i370 > 0 and path1_i370 != path1_i371 and path1_i370 < path1_i371 and path1_i375 != 0 and path1_i375 != 0 and path1_i378 != path1_i392 and path1_i378 != path1_i392)) or ((path2_i358 = path2_i368 and path2_i359 = path2_i371 and path2_i368 = path2_i370 and path2_i383 = (path2_i370 + -1) and path2_i393 = (path2_i371 - 2) and path2_i383 = res_i358 and path2_i371 = res_i359 and 0 = res_i360 and path2_i358 = initial_i358 and path2_i359 = initial_i359 and path2_i360 = initial_i360) and (T and 0 = 0 and 0 <= path2_i368 and path2_i368 <= path2_i359 and path2_i368 <= path2_i359 and path2_i370 > 0 and path2_i370 != path2_i371 and path2_i370 < path2_i371 and path2_i360 = 0 and T and T and path2_i383 != path2_i393 and path2_i383 != path2_i393)) or ((path3_i358 = path3_i368 and path3_i359 = path3_i374 and path3_i395 = (path3_i374 - 2) and path3_i395 = path3_i410 and 1 = res_i358 and 1 = res_i360 and path3_i374 = res_i359 and path3_i358 = initial_i358 and path3_i359 = initial_i359 and path3_i360 = initial_i360) and (T and 0 = 0 and 0 <= path3_i368 and path3_i368 <= path3_i359 and path3_i368 <= path3_i359 and path3_i368 = 0 and T and T and 0 = 0 and 0 < path3_i374 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 > path3_i410)) or ((path4_i358 = path4_i368 and path4_i359 = path4_i374 and path4_i395 = (path4_i374 - 2) and path4_i374 = path4_i412 and path4_i395 = path4_i411 and 1 = res_i358 and 1 = res_i360 and path4_i412 = res_i359 and path4_i358 = initial_i358 and path4_i359 = initial_i359 and path4_i360 = initial_i360) and (T and 0 = 0 and 0 <= path4_i368 and path4_i368 <= path4_i359 and path4_i368 <= path4_i359 and path4_i368 = 0 and T and T and 0 = 0 and 0 < path4_i374 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 < path4_i411)) or ((path5_i358 = path5_i368 and path5_i359 = path5_i371 and path5_i368 = path5_i370 and path5_i360 = path5_i375 and path5_i378 = (path5_i370 + 1) and path5_i392 = (path5_i371 - 2) and path5_i413 = (path5_i371 + -1) and path5_i392 = res_i358 and path5_i413 = res_i359 and path5_i375 = res_i360 and path5_i358 = initial_i358 and path5_i359 = initial_i359 and path5_i360 = initial_i360) and (T and 0 = 0 and 0 <= path5_i368 and path5_i368 <= path5_i359 and path5_i368 <= path5_i359 and path5_i370 > 0 and path5_i370 != path5_i371 and path5_i370 < path5_i371 and path5_i375 != 0 and path5_i375 != 0 and path5_i378 = path5_i392 and path5_i392 = path5_i392)) or ((path6_i358 = path6_i368 and path6_i359 = path6_i371 and path6_i368 = path6_i370 and path6_i383 = (path6_i370 + -1) and path6_i393 = (path6_i371 - 2) and path6_i414 = (path6_i371 + -1) and path6_i393 = res_i358 and path6_i414 = res_i359 and 0 = res_i360 and path6_i358 = initial_i358 and path6_i359 = initial_i359 and path6_i360 = initial_i360) and (T and 0 = 0 and 0 <= path6_i368 and path6_i368 <= path6_i359 and path6_i368 <= path6_i359 and path6_i370 > 0 and path6_i370 != path6_i371 and path6_i370 < path6_i371 and path6_i360 = 0 and T and T and path6_i383 = path6_i393 and path6_i393 = path6_i393)) or ((path7_i358 = path7_i368 and path7_i359 = path7_i371 and path7_i368 = path7_i370 and path7_i387 = (path7_i371 + -1) and path7_i387 = path7_i383 and path7_i393 = (path7_i371 - 2) and path7_i383 = res_i358 and path7_i371 = res_i359 and 0 = res_i360 and path7_i358 = initial_i358 and path7_i359 = initial_i359 and path7_i360 = initial_i360) and (T and 0 = 0 and 0 <= path7_i368 and path7_i368 <= path7_i359 and path7_i368 <= path7_i359 and path7_i370 > 0 and path7_i370 = path7_i371 and path7_i371 = path7_i371 and T and T and path7_i383 != path7_i393 and path7_i383 != path7_i393)) or ((path9_i358 = path9_i368 and path9_i359 = path9_i374 and path9_i395 = (path9_i374 - 2) and path9_i429 = (path9_i374 + -1) and 1 = res_i358 and 1 = res_i360 and path9_i429 = res_i359 and path9_i358 = initial_i358 and path9_i359 = initial_i359 and path9_i360 = initial_i360) and (T and 0 = 0 and 0 <= path9_i368 and path9_i368 <= path9_i359 and path9_i368 <= path9_i359 and path9_i368 = 0 and T and T and 0 = 0 and 0 < path9_i374 and 1 > 0 and 1 > 0 and T and path9_i395 = 1)) or ((path10_i358 = path10_i368 and path10_i359 = path10_i371 and path10_i368 = path10_i370 and path10_i387 = (path10_i371 + -1) and path10_i387 = path10_i383 and path10_i393 = (path10_i371 - 2) and path10_i414 = (path10_i371 + -1) and path10_i393 = res_i358 and path10_i414 = res_i359 and 0 = res_i360 and path10_i358 = initial_i358 and path10_i359 = initial_i359 and path10_i360 = initial_i360) and (T and 0 = 0 and 0 <= path10_i368 and path10_i368 <= path10_i359 and path10_i368 <= path10_i359 and path10_i370 > 0 and path10_i370 = path10_i371 and path10_i371 = path10_i371 and T and T and path10_i383 = path10_i393 and path10_i393 = path10_i393)) or ((path1_i358 = path1_i368 and path1_i359 = path1_i371 and path1_i368 = path1_i370 and path1_i360 = path1_i375 and path1_i378 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i378 = res_i358 and path1_i371 = res_i359 and path1_i375 = res_i360 and path1_i358 = initial_i358 and path1_i359 = initial_i359 and path1_i360 = initial_i360) and (T and 0 = 0 and 0 <= path1_i368 and path1_i368 <= path1_i359 and path1_i368 <= path1_i359 and path1_i370 > 0 and path1_i370 < path1_i371 and path1_i375 != 0 and path1_i375 != 0 and path1_i378 != path1_i392 and path1_i378 != path1_i392 and path1_i370 < path1_i371)) or ((path1_i358 = path1_i368 and path1_i359 = path1_i371 and path1_i368 = path1_i370 and path1_i360 = path1_i375 and path1_i378 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i378 = res_i358 and path1_i371 = res_i359 and path1_i375 = res_i360 and path1_i358 = initial_i358 and path1_i359 = initial_i359 and path1_i360 = initial_i360) and (T and 0 = 0 and 0 <= path1_i368 and path1_i368 <= path1_i359 and path1_i368 <= path1_i359 and path1_i370 > 0 and path1_i370 < path1_i371 and path1_i375 != 0 and path1_i375 != 0 and path1_i378 != path1_i392 and path1_i378 != path1_i392 and path1_i370 > path1_i371)) or ((path1_i358 = path1_i368 and path1_i359 = path1_i371 and path1_i368 = path1_i370 and path1_i360 = path1_i375 and path1_i378 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i378 = res_i358 and path1_i371 = res_i359 and path1_i375 = res_i360 and path1_i358 = initial_i358 and path1_i359 = initial_i359 and path1_i360 = initial_i360) and (T and 0 = 0 and 0 <= path1_i368 and path1_i368 <= path1_i359 and path1_i368 <= path1_i359 and path1_i370 > 0 and path1_i370 != path1_i371 and path1_i370 < path1_i371 and path1_i375 != 0 and path1_i378 != path1_i392 and path1_i378 != path1_i392 and path1_i375 < 0)) or ((path1_i358 = path1_i368 and path1_i359 = path1_i371 and path1_i368 = path1_i370 and path1_i360 = path1_i375 and path1_i378 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i378 = res_i358 and path1_i371 = res_i359 and path1_i375 = res_i360 and path1_i358 = initial_i358 and path1_i359 = initial_i359 and path1_i360 = initial_i360) and (T and 0 = 0 and 0 <= path1_i368 and path1_i368 <= path1_i359 and path1_i368 <= path1_i359 and path1_i370 > 0 and path1_i370 != path1_i371 and path1_i370 < path1_i371 and path1_i375 != 0 and path1_i378 != path1_i392 and path1_i378 != path1_i392 and path1_i375 > 0))) and (((res1_i358 = res1_i368 and res1_i359 = res1_i371 and res1_i368 = res1_i370 and res1_i360 = res1_i375 and res1_i378 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i358 = res1_i358 and res_i359 = res1_i359 and res_i360 = res1_i360) and !(T and 0 = 0 and 0 <= res1_i368 and res1_i368 <= res1_i359 and res1_i368 <= res1_i359 and res1_i370 > 0 and res1_i370 != res1_i371 and res1_i370 < res1_i371 and res1_i375 != 0 and res1_i375 != 0 and res1_i378 != res1_i392 and res1_i378 != res1_i392)) and ((res2_i358 = res2_i368 and res2_i359 = res2_i371 and res2_i368 = res2_i370 and res2_i383 = (res2_i370 + -1) and res2_i393 = (res2_i371 - 2) and res_i358 = res2_i358 and res_i359 = res2_i359 and res_i360 = res2_i360) and !(T and 0 = 0 and 0 <= res2_i368 and res2_i368 <= res2_i359 and res2_i368 <= res2_i359 and res2_i370 > 0 and res2_i370 != res2_i371 and res2_i370 < res2_i371 and res2_i360 = 0 and T and T and res2_i383 != res2_i393 and res2_i383 != res2_i393)) and ((res3_i358 = res3_i368 and res3_i359 = res3_i374 and res3_i395 = (res3_i374 - 2) and res3_i395 = res3_i410 and res_i358 = res3_i358 and res_i359 = res3_i359 and res_i360 = res3_i360) and !(T and 0 = 0 and 0 <= res3_i368 and res3_i368 <= res3_i359 and res3_i368 <= res3_i359 and res3_i368 = 0 and T and T and 0 = 0 and 0 < res3_i374 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 > res3_i410)) and ((res4_i358 = res4_i368 and res4_i359 = res4_i374 and res4_i395 = (res4_i374 - 2) and res4_i374 = res4_i412 and res4_i395 = res4_i411 and res_i358 = res4_i358 and res_i359 = res4_i359 and res_i360 = res4_i360) and !(T and 0 = 0 and 0 <= res4_i368 and res4_i368 <= res4_i359 and res4_i368 <= res4_i359 and res4_i368 = 0 and T and T and 0 = 0 and 0 < res4_i374 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 < res4_i411)) and ((res5_i358 = res5_i368 and res5_i359 = res5_i371 and res5_i368 = res5_i370 and res5_i360 = res5_i375 and res5_i378 = (res5_i370 + 1) and res5_i392 = (res5_i371 - 2) and res5_i413 = (res5_i371 + -1) and res_i358 = res5_i358 and res_i359 = res5_i359 and res_i360 = res5_i360) and !(T and 0 = 0 and 0 <= res5_i368 and res5_i368 <= res5_i359 and res5_i368 <= res5_i359 and res5_i370 > 0 and res5_i370 != res5_i371 and res5_i370 < res5_i371 and res5_i375 != 0 and res5_i375 != 0 and res5_i378 = res5_i392 and res5_i392 = res5_i392)) and ((res6_i358 = res6_i368 and res6_i359 = res6_i371 and res6_i368 = res6_i370 and res6_i383 = (res6_i370 + -1) and res6_i393 = (res6_i371 - 2) and res6_i414 = (res6_i371 + -1) and res_i358 = res6_i358 and res_i359 = res6_i359 and res_i360 = res6_i360) and !(T and 0 = 0 and 0 <= res6_i368 and res6_i368 <= res6_i359 and res6_i368 <= res6_i359 and res6_i370 > 0 and res6_i370 != res6_i371 and res6_i370 < res6_i371 and res6_i360 = 0 and T and T and res6_i383 = res6_i393 and res6_i393 = res6_i393)) and ((res7_i358 = res7_i368 and res7_i359 = res7_i371 and res7_i368 = res7_i370 and res7_i387 = (res7_i371 + -1) and res7_i387 = res7_i383 and res7_i393 = (res7_i371 - 2) and res_i358 = res7_i358 and res_i359 = res7_i359 and res_i360 = res7_i360) and !(T and 0 = 0 and 0 <= res7_i368 and res7_i368 <= res7_i359 and res7_i368 <= res7_i359 and res7_i370 > 0 and res7_i370 = res7_i371 and res7_i371 = res7_i371 and T and T and res7_i383 != res7_i393 and res7_i383 != res7_i393)) and ((res9_i358 = res9_i368 and res9_i359 = res9_i374 and res9_i395 = (res9_i374 - 2) and res9_i429 = (res9_i374 + -1) and res_i358 = res9_i358 and res_i359 = res9_i359 and res_i360 = res9_i360) and !(T and 0 = 0 and 0 <= res9_i368 and res9_i368 <= res9_i359 and res9_i368 <= res9_i359 and res9_i368 = 0 and T and T and 0 = 0 and 0 < res9_i374 and 1 > 0 and 1 > 0 and T and res9_i395 = 1)) and ((res10_i358 = res10_i368 and res10_i359 = res10_i371 and res10_i368 = res10_i370 and res10_i387 = (res10_i371 + -1) and res10_i387 = res10_i383 and res10_i393 = (res10_i371 - 2) and res10_i414 = (res10_i371 + -1) and res_i358 = res10_i358 and res_i359 = res10_i359 and res_i360 = res10_i360) and !(T and 0 = 0 and 0 <= res10_i368 and res10_i368 <= res10_i359 and res10_i368 <= res10_i359 and res10_i370 > 0 and res10_i370 = res10_i371 and res10_i371 = res10_i371 and T and T and res10_i383 = res10_i393 and res10_i393 = res10_i393)) and ((res1_i358 = res1_i368 and res1_i359 = res1_i371 and res1_i368 = res1_i370 and res1_i360 = res1_i375 and res1_i378 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i358 = res1_i358 and res_i359 = res1_i359 and res_i360 = res1_i360) and !(T and 0 = 0 and 0 <= res1_i368 and res1_i368 <= res1_i359 and res1_i368 <= res1_i359 and res1_i370 > 0 and res1_i370 < res1_i371 and res1_i375 != 0 and res1_i375 != 0 and res1_i378 != res1_i392 and res1_i378 != res1_i392 and res1_i370 < res1_i371)) and ((res1_i358 = res1_i368 and res1_i359 = res1_i371 and res1_i368 = res1_i370 and res1_i360 = res1_i375 and res1_i378 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i358 = res1_i358 and res_i359 = res1_i359 and res_i360 = res1_i360) and !(T and 0 = 0 and 0 <= res1_i368 and res1_i368 <= res1_i359 and res1_i368 <= res1_i359 and res1_i370 > 0 and res1_i370 < res1_i371 and res1_i375 != 0 and res1_i375 != 0 and res1_i378 != res1_i392 and res1_i378 != res1_i392 and res1_i370 > res1_i371)) and ((res1_i358 = res1_i368 and res1_i359 = res1_i371 and res1_i368 = res1_i370 and res1_i360 = res1_i375 and res1_i378 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i358 = res1_i358 and res_i359 = res1_i359 and res_i360 = res1_i360) and !(T and 0 = 0 and 0 <= res1_i368 and res1_i368 <= res1_i359 and res1_i368 <= res1_i359 and res1_i370 > 0 and res1_i370 != res1_i371 and res1_i370 < res1_i371 and res1_i375 != 0 and res1_i378 != res1_i392 and res1_i378 != res1_i392 and res1_i375 < 0)) and ((res1_i358 = res1_i368 and res1_i359 = res1_i371 and res1_i368 = res1_i370 and res1_i360 = res1_i375 and res1_i378 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i358 = res1_i358 and res_i359 = res1_i359 and res_i360 = res1_i360) and !(T and 0 = 0 and 0 <= res1_i368 and res1_i368 <= res1_i359 and res1_i368 <= res1_i359 and res1_i370 > 0 and res1_i370 != res1_i371 and res1_i370 < res1_i371 and res1_i375 != 0 and res1_i378 != res1_i392 and res1_i378 != res1_i392 and res1_i375 > 0))))) 31.50/9.75 31.50/9.75 to be UNSAT. Consequently, the loop will not terminate. 31.50/9.75 ---------------------------------------- 31.50/9.75 31.50/9.75 (6) 31.50/9.75 NO 31.76/9.79 EOF