/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: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 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, 818 ms] (4) JBCTerminationGraph (5) JBCNonTerm [COMPLETE, 9833 ms] (6) NO ---------------------------------------- (0) Obligation: need to prove termination of the following program: package simple.narrowing; public class Main { /** * @param args */ public static void main(String[] args) { Narrowing.loop(args.length); } } package simple.narrowing; public class Narrowing { public static void loop(int i) { int range = 20; boolean up = false; while (0 <= i && i <= range) { if (i == 0) { up = true; } if (i == range) { up = false; } if (up) { i++; } if (!up) { i--; } if (i == range-2) { range--; } } } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: package simple.narrowing; public class Main { /** * @param args */ public static void main(String[] args) { Narrowing.loop(args.length); } } package simple.narrowing; public class Narrowing { public static void loop(int i) { int range = 20; boolean up = false; while (0 <= i && i <= range) { if (i == 0) { up = true; } if (i == range) { up = false; } if (up) { i++; } if (!up) { i--; } if (i == range-2) { range--; } } } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: simple.narrowing.Main.main([Ljava/lang/String;)V: Graph of 117 nodes with 1 SCC. ---------------------------------------- (5) JBCNonTerm (COMPLETE) Reached a loop using the following run: 0: a238([java.lang.String...]): length 1 -->{java.lang.Object...} YES: (JL1) 1: a238([java.lang.String...]): length 1 -->{java.lang.Object...} YES: (JL1) 2: YES: (JL1) 3: YES: (JL1) 4: YES: (JL1) 5: YES: (JL1) 6: YES: (JL1) 7: YES: (JL1) Start state of loop: [a66(lv_0_0)] i362: # i363: # i364: # i21: [0,+inf)(l1) a66([java.lang.String...]): length i21 -->{java.lang.Object...} YES: (JL1) In the loop head node, references [i362, i363, i364] 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_i21 and ((((path1_i362 = path1_i372 and path1_i363 = path1_i374 and path1_i372 = path1_i373 and path1_i364 = path1_i378 and path1_i381 = (path1_i373 + 1) and path1_i396 = (path1_i374 - 2) and path1_i381 = res_i362 and path1_i374 = res_i363 and path1_i378 = res_i364 and path1_i362 = initial_i362 and path1_i363 = initial_i363 and path1_i364 = initial_i364) and (T and 0 = 0 and 0 <= path1_i372 and path1_i372 <= path1_i363 and path1_i372 <= path1_i363 and path1_i373 > 0 and path1_i373 != path1_i374 and path1_i373 < path1_i374 and path1_i378 != 0 and path1_i378 != 0 and path1_i381 != path1_i396 and path1_i381 != path1_i396)) or ((path2_i362 = path2_i372 and path2_i363 = path2_i374 and path2_i372 = path2_i373 and path2_i386 = (path2_i373 + -1) and path2_i397 = (path2_i374 - 2) and path2_i386 = res_i362 and path2_i374 = res_i363 and 0 = res_i364 and path2_i362 = initial_i362 and path2_i363 = initial_i363 and path2_i364 = initial_i364) and (T and 0 = 0 and 0 <= path2_i372 and path2_i372 <= path2_i363 and path2_i372 <= path2_i363 and path2_i373 > 0 and path2_i373 != path2_i374 and path2_i373 < path2_i374 and path2_i364 = 0 and T and T and path2_i386 != path2_i397 and path2_i386 != path2_i397)) or ((path3_i362 = path3_i372 and path3_i363 = path3_i377 and path3_i399 = (path3_i377 - 2) and path3_i399 = path3_i415 and 1 = res_i362 and 1 = res_i364 and path3_i377 = res_i363 and path3_i362 = initial_i362 and path3_i363 = initial_i363 and path3_i364 = initial_i364) and (T and 0 = 0 and 0 <= path3_i372 and path3_i372 <= path3_i363 and path3_i372 <= path3_i363 and path3_i372 = 0 and T and T and 0 = 0 and 0 < path3_i377 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 > path3_i415)) or ((path4_i362 = path4_i372 and path4_i363 = path4_i377 and path4_i399 = (path4_i377 - 2) and path4_i377 = path4_i417 and path4_i399 = path4_i416 and 1 = res_i362 and 1 = res_i364 and path4_i417 = res_i363 and path4_i362 = initial_i362 and path4_i363 = initial_i363 and path4_i364 = initial_i364) and (T and 0 = 0 and 0 <= path4_i372 and path4_i372 <= path4_i363 and path4_i372 <= path4_i363 and path4_i372 = 0 and T and T and 0 = 0 and 0 < path4_i377 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 < path4_i416)) or ((path5_i362 = path5_i372 and path5_i363 = path5_i374 and path5_i372 = path5_i373 and path5_i364 = path5_i378 and path5_i381 = (path5_i373 + 1) and path5_i396 = (path5_i374 - 2) and path5_i418 = (path5_i374 + -1) and path5_i396 = res_i362 and path5_i418 = res_i363 and path5_i378 = res_i364 and path5_i362 = initial_i362 and path5_i363 = initial_i363 and path5_i364 = initial_i364) and (T and 0 = 0 and 0 <= path5_i372 and path5_i372 <= path5_i363 and path5_i372 <= path5_i363 and path5_i373 > 0 and path5_i373 != path5_i374 and path5_i373 < path5_i374 and path5_i378 != 0 and path5_i378 != 0 and path5_i381 = path5_i396 and path5_i396 = path5_i396)) or ((path6_i362 = path6_i372 and path6_i363 = path6_i374 and path6_i372 = path6_i373 and path6_i386 = (path6_i373 + -1) and path6_i397 = (path6_i374 - 2) and path6_i419 = (path6_i374 + -1) and path6_i397 = res_i362 and path6_i419 = res_i363 and 0 = res_i364 and path6_i362 = initial_i362 and path6_i363 = initial_i363 and path6_i364 = initial_i364) and (T and 0 = 0 and 0 <= path6_i372 and path6_i372 <= path6_i363 and path6_i372 <= path6_i363 and path6_i373 > 0 and path6_i373 != path6_i374 and path6_i373 < path6_i374 and path6_i364 = 0 and T and T and path6_i386 = path6_i397 and path6_i397 = path6_i397)) or ((path7_i362 = path7_i372 and path7_i363 = path7_i374 and path7_i372 = path7_i373 and path7_i390 = (path7_i374 + -1) and path7_i390 = path7_i386 and path7_i397 = (path7_i374 - 2) and path7_i386 = res_i362 and path7_i374 = res_i363 and 0 = res_i364 and path7_i362 = initial_i362 and path7_i363 = initial_i363 and path7_i364 = initial_i364) and (T and 0 = 0 and 0 <= path7_i372 and path7_i372 <= path7_i363 and path7_i372 <= path7_i363 and path7_i373 > 0 and path7_i373 = path7_i374 and path7_i374 = path7_i374 and T and T and path7_i386 != path7_i397 and path7_i386 != path7_i397)) or ((path9_i362 = path9_i372 and path9_i363 = path9_i377 and path9_i399 = (path9_i377 - 2) and path9_i434 = (path9_i377 + -1) and 1 = res_i362 and 1 = res_i364 and path9_i434 = res_i363 and path9_i362 = initial_i362 and path9_i363 = initial_i363 and path9_i364 = initial_i364) and (T and 0 = 0 and 0 <= path9_i372 and path9_i372 <= path9_i363 and path9_i372 <= path9_i363 and path9_i372 = 0 and T and T and 0 = 0 and 0 < path9_i377 and 1 > 0 and 1 > 0 and T and path9_i399 = 1)) or ((path10_i362 = path10_i372 and path10_i363 = path10_i374 and path10_i372 = path10_i373 and path10_i390 = (path10_i374 + -1) and path10_i390 = path10_i386 and path10_i397 = (path10_i374 - 2) and path10_i419 = (path10_i374 + -1) and path10_i397 = res_i362 and path10_i419 = res_i363 and 0 = res_i364 and path10_i362 = initial_i362 and path10_i363 = initial_i363 and path10_i364 = initial_i364) and (T and 0 = 0 and 0 <= path10_i372 and path10_i372 <= path10_i363 and path10_i372 <= path10_i363 and path10_i373 > 0 and path10_i373 = path10_i374 and path10_i374 = path10_i374 and T and T and path10_i386 = path10_i397 and path10_i397 = path10_i397)) or ((path1_i362 = path1_i372 and path1_i363 = path1_i374 and path1_i372 = path1_i373 and path1_i364 = path1_i378 and path1_i381 = (path1_i373 + 1) and path1_i396 = (path1_i374 - 2) and path1_i381 = res_i362 and path1_i374 = res_i363 and path1_i378 = res_i364 and path1_i362 = initial_i362 and path1_i363 = initial_i363 and path1_i364 = initial_i364) and (T and 0 = 0 and 0 <= path1_i372 and path1_i372 <= path1_i363 and path1_i372 <= path1_i363 and path1_i373 > 0 and path1_i373 < path1_i374 and path1_i378 != 0 and path1_i378 != 0 and path1_i381 != path1_i396 and path1_i381 != path1_i396 and path1_i373 < path1_i374)) or ((path1_i362 = path1_i372 and path1_i363 = path1_i374 and path1_i372 = path1_i373 and path1_i364 = path1_i378 and path1_i381 = (path1_i373 + 1) and path1_i396 = (path1_i374 - 2) and path1_i381 = res_i362 and path1_i374 = res_i363 and path1_i378 = res_i364 and path1_i362 = initial_i362 and path1_i363 = initial_i363 and path1_i364 = initial_i364) and (T and 0 = 0 and 0 <= path1_i372 and path1_i372 <= path1_i363 and path1_i372 <= path1_i363 and path1_i373 > 0 and path1_i373 < path1_i374 and path1_i378 != 0 and path1_i378 != 0 and path1_i381 != path1_i396 and path1_i381 != path1_i396 and path1_i373 > path1_i374)) or ((path1_i362 = path1_i372 and path1_i363 = path1_i374 and path1_i372 = path1_i373 and path1_i364 = path1_i378 and path1_i381 = (path1_i373 + 1) and path1_i396 = (path1_i374 - 2) and path1_i381 = res_i362 and path1_i374 = res_i363 and path1_i378 = res_i364 and path1_i362 = initial_i362 and path1_i363 = initial_i363 and path1_i364 = initial_i364) and (T and 0 = 0 and 0 <= path1_i372 and path1_i372 <= path1_i363 and path1_i372 <= path1_i363 and path1_i373 > 0 and path1_i373 != path1_i374 and path1_i373 < path1_i374 and path1_i378 != 0 and path1_i381 != path1_i396 and path1_i381 != path1_i396 and path1_i378 < 0)) or ((path1_i362 = path1_i372 and path1_i363 = path1_i374 and path1_i372 = path1_i373 and path1_i364 = path1_i378 and path1_i381 = (path1_i373 + 1) and path1_i396 = (path1_i374 - 2) and path1_i381 = res_i362 and path1_i374 = res_i363 and path1_i378 = res_i364 and path1_i362 = initial_i362 and path1_i363 = initial_i363 and path1_i364 = initial_i364) and (T and 0 = 0 and 0 <= path1_i372 and path1_i372 <= path1_i363 and path1_i372 <= path1_i363 and path1_i373 > 0 and path1_i373 != path1_i374 and path1_i373 < path1_i374 and path1_i378 != 0 and path1_i381 != path1_i396 and path1_i381 != path1_i396 and path1_i378 > 0))) and (((res1_i362 = res1_i372 and res1_i363 = res1_i374 and res1_i372 = res1_i373 and res1_i364 = res1_i378 and res1_i381 = (res1_i373 + 1) and res1_i396 = (res1_i374 - 2) and res_i362 = res1_i362 and res_i363 = res1_i363 and res_i364 = res1_i364) and !(T and 0 = 0 and 0 <= res1_i372 and res1_i372 <= res1_i363 and res1_i372 <= res1_i363 and res1_i373 > 0 and res1_i373 != res1_i374 and res1_i373 < res1_i374 and res1_i378 != 0 and res1_i378 != 0 and res1_i381 != res1_i396 and res1_i381 != res1_i396)) and ((res2_i362 = res2_i372 and res2_i363 = res2_i374 and res2_i372 = res2_i373 and res2_i386 = (res2_i373 + -1) and res2_i397 = (res2_i374 - 2) and res_i362 = res2_i362 and res_i363 = res2_i363 and res_i364 = res2_i364) and !(T and 0 = 0 and 0 <= res2_i372 and res2_i372 <= res2_i363 and res2_i372 <= res2_i363 and res2_i373 > 0 and res2_i373 != res2_i374 and res2_i373 < res2_i374 and res2_i364 = 0 and T and T and res2_i386 != res2_i397 and res2_i386 != res2_i397)) and ((res3_i362 = res3_i372 and res3_i363 = res3_i377 and res3_i399 = (res3_i377 - 2) and res3_i399 = res3_i415 and res_i362 = res3_i362 and res_i363 = res3_i363 and res_i364 = res3_i364) and !(T and 0 = 0 and 0 <= res3_i372 and res3_i372 <= res3_i363 and res3_i372 <= res3_i363 and res3_i372 = 0 and T and T and 0 = 0 and 0 < res3_i377 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 > res3_i415)) and ((res4_i362 = res4_i372 and res4_i363 = res4_i377 and res4_i399 = (res4_i377 - 2) and res4_i377 = res4_i417 and res4_i399 = res4_i416 and res_i362 = res4_i362 and res_i363 = res4_i363 and res_i364 = res4_i364) and !(T and 0 = 0 and 0 <= res4_i372 and res4_i372 <= res4_i363 and res4_i372 <= res4_i363 and res4_i372 = 0 and T and T and 0 = 0 and 0 < res4_i377 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 < res4_i416)) and ((res5_i362 = res5_i372 and res5_i363 = res5_i374 and res5_i372 = res5_i373 and res5_i364 = res5_i378 and res5_i381 = (res5_i373 + 1) and res5_i396 = (res5_i374 - 2) and res5_i418 = (res5_i374 + -1) and res_i362 = res5_i362 and res_i363 = res5_i363 and res_i364 = res5_i364) and !(T and 0 = 0 and 0 <= res5_i372 and res5_i372 <= res5_i363 and res5_i372 <= res5_i363 and res5_i373 > 0 and res5_i373 != res5_i374 and res5_i373 < res5_i374 and res5_i378 != 0 and res5_i378 != 0 and res5_i381 = res5_i396 and res5_i396 = res5_i396)) and ((res6_i362 = res6_i372 and res6_i363 = res6_i374 and res6_i372 = res6_i373 and res6_i386 = (res6_i373 + -1) and res6_i397 = (res6_i374 - 2) and res6_i419 = (res6_i374 + -1) and res_i362 = res6_i362 and res_i363 = res6_i363 and res_i364 = res6_i364) and !(T and 0 = 0 and 0 <= res6_i372 and res6_i372 <= res6_i363 and res6_i372 <= res6_i363 and res6_i373 > 0 and res6_i373 != res6_i374 and res6_i373 < res6_i374 and res6_i364 = 0 and T and T and res6_i386 = res6_i397 and res6_i397 = res6_i397)) and ((res7_i362 = res7_i372 and res7_i363 = res7_i374 and res7_i372 = res7_i373 and res7_i390 = (res7_i374 + -1) and res7_i390 = res7_i386 and res7_i397 = (res7_i374 - 2) and res_i362 = res7_i362 and res_i363 = res7_i363 and res_i364 = res7_i364) and !(T and 0 = 0 and 0 <= res7_i372 and res7_i372 <= res7_i363 and res7_i372 <= res7_i363 and res7_i373 > 0 and res7_i373 = res7_i374 and res7_i374 = res7_i374 and T and T and res7_i386 != res7_i397 and res7_i386 != res7_i397)) and ((res9_i362 = res9_i372 and res9_i363 = res9_i377 and res9_i399 = (res9_i377 - 2) and res9_i434 = (res9_i377 + -1) and res_i362 = res9_i362 and res_i363 = res9_i363 and res_i364 = res9_i364) and !(T and 0 = 0 and 0 <= res9_i372 and res9_i372 <= res9_i363 and res9_i372 <= res9_i363 and res9_i372 = 0 and T and T and 0 = 0 and 0 < res9_i377 and 1 > 0 and 1 > 0 and T and res9_i399 = 1)) and ((res10_i362 = res10_i372 and res10_i363 = res10_i374 and res10_i372 = res10_i373 and res10_i390 = (res10_i374 + -1) and res10_i390 = res10_i386 and res10_i397 = (res10_i374 - 2) and res10_i419 = (res10_i374 + -1) and res_i362 = res10_i362 and res_i363 = res10_i363 and res_i364 = res10_i364) and !(T and 0 = 0 and 0 <= res10_i372 and res10_i372 <= res10_i363 and res10_i372 <= res10_i363 and res10_i373 > 0 and res10_i373 = res10_i374 and res10_i374 = res10_i374 and T and T and res10_i386 = res10_i397 and res10_i397 = res10_i397)) and ((res1_i362 = res1_i372 and res1_i363 = res1_i374 and res1_i372 = res1_i373 and res1_i364 = res1_i378 and res1_i381 = (res1_i373 + 1) and res1_i396 = (res1_i374 - 2) and res_i362 = res1_i362 and res_i363 = res1_i363 and res_i364 = res1_i364) and !(T and 0 = 0 and 0 <= res1_i372 and res1_i372 <= res1_i363 and res1_i372 <= res1_i363 and res1_i373 > 0 and res1_i373 < res1_i374 and res1_i378 != 0 and res1_i378 != 0 and res1_i381 != res1_i396 and res1_i381 != res1_i396 and res1_i373 < res1_i374)) and ((res1_i362 = res1_i372 and res1_i363 = res1_i374 and res1_i372 = res1_i373 and res1_i364 = res1_i378 and res1_i381 = (res1_i373 + 1) and res1_i396 = (res1_i374 - 2) and res_i362 = res1_i362 and res_i363 = res1_i363 and res_i364 = res1_i364) and !(T and 0 = 0 and 0 <= res1_i372 and res1_i372 <= res1_i363 and res1_i372 <= res1_i363 and res1_i373 > 0 and res1_i373 < res1_i374 and res1_i378 != 0 and res1_i378 != 0 and res1_i381 != res1_i396 and res1_i381 != res1_i396 and res1_i373 > res1_i374)) and ((res1_i362 = res1_i372 and res1_i363 = res1_i374 and res1_i372 = res1_i373 and res1_i364 = res1_i378 and res1_i381 = (res1_i373 + 1) and res1_i396 = (res1_i374 - 2) and res_i362 = res1_i362 and res_i363 = res1_i363 and res_i364 = res1_i364) and !(T and 0 = 0 and 0 <= res1_i372 and res1_i372 <= res1_i363 and res1_i372 <= res1_i363 and res1_i373 > 0 and res1_i373 != res1_i374 and res1_i373 < res1_i374 and res1_i378 != 0 and res1_i381 != res1_i396 and res1_i381 != res1_i396 and res1_i378 < 0)) and ((res1_i362 = res1_i372 and res1_i363 = res1_i374 and res1_i372 = res1_i373 and res1_i364 = res1_i378 and res1_i381 = (res1_i373 + 1) and res1_i396 = (res1_i374 - 2) and res_i362 = res1_i362 and res_i363 = res1_i363 and res_i364 = res1_i364) and !(T and 0 = 0 and 0 <= res1_i372 and res1_i372 <= res1_i363 and res1_i372 <= res1_i363 and res1_i373 > 0 and res1_i373 != res1_i374 and res1_i373 < res1_i374 and res1_i378 != 0 and res1_i381 != res1_i396 and res1_i381 != res1_i396 and res1_i378 > 0))))) to be UNSAT. Consequently, the loop will not terminate. ---------------------------------------- (6) NO