/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty termination of the given Bare JBC problem could be disproven: (0) Bare JBC problem (1) BareJBCToJBCProof [EQUIVALENT, 97 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 796 ms] (4) JBCTerminationGraph (5) JBCNonTerm [COMPLETE, 4913 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: a257([java.lang.String...]): length 1 -->{java.lang.Object...} YES: (JL1) 1: a257([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)] i359: # i360: # i361: # i18: [0,+inf)(l1) a66([java.lang.String...]): length i18 -->{java.lang.Object...} YES: (JL1) In the loop head node, references [i359, i360, i361] 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_i18 and ((((path1_i359 = path1_i369 and path1_i360 = path1_i371 and path1_i369 = path1_i370 and path1_i361 = path1_i374 and path1_i377 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i377 = res_i359 and path1_i371 = res_i360 and path1_i374 = res_i361 and path1_i359 = initial_i359 and path1_i360 = initial_i360 and path1_i361 = initial_i361) and (T and 0 = 0 and 0 <= path1_i369 and path1_i369 <= path1_i360 and path1_i369 <= path1_i360 and path1_i370 > 0 and path1_i370 != path1_i371 and path1_i370 < path1_i371 and path1_i374 != 0 and path1_i374 != 0 and path1_i377 != path1_i392 and path1_i377 != path1_i392)) or ((path2_i359 = path2_i369 and path2_i360 = path2_i371 and path2_i369 = path2_i370 and path2_i382 = (path2_i370 + -1) and path2_i393 = (path2_i371 - 2) and path2_i382 = res_i359 and path2_i371 = res_i360 and 0 = res_i361 and path2_i359 = initial_i359 and path2_i360 = initial_i360 and path2_i361 = initial_i361) and (T and 0 = 0 and 0 <= path2_i369 and path2_i369 <= path2_i360 and path2_i369 <= path2_i360 and path2_i370 > 0 and path2_i370 != path2_i371 and path2_i370 < path2_i371 and path2_i361 = 0 and T and T and path2_i382 != path2_i393 and path2_i382 != path2_i393)) or ((path3_i359 = path3_i369 and path3_i360 = path3_i373 and path3_i395 = (path3_i373 - 2) and path3_i395 = path3_i410 and 1 = res_i359 and 1 = res_i361 and path3_i373 = res_i360 and path3_i359 = initial_i359 and path3_i360 = initial_i360 and path3_i361 = initial_i361) and (T and 0 = 0 and 0 <= path3_i369 and path3_i369 <= path3_i360 and path3_i369 <= path3_i360 and path3_i369 = 0 and T and T and 0 = 0 and 0 < path3_i373 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 > path3_i410)) or ((path4_i359 = path4_i369 and path4_i360 = path4_i373 and path4_i395 = (path4_i373 - 2) and path4_i373 = path4_i412 and path4_i395 = path4_i411 and 1 = res_i359 and 1 = res_i361 and path4_i412 = res_i360 and path4_i359 = initial_i359 and path4_i360 = initial_i360 and path4_i361 = initial_i361) and (T and 0 = 0 and 0 <= path4_i369 and path4_i369 <= path4_i360 and path4_i369 <= path4_i360 and path4_i369 = 0 and T and T and 0 = 0 and 0 < path4_i373 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 < path4_i411)) or ((path5_i359 = path5_i369 and path5_i360 = path5_i371 and path5_i369 = path5_i370 and path5_i361 = path5_i374 and path5_i377 = (path5_i370 + 1) and path5_i392 = (path5_i371 - 2) and path5_i414 = (path5_i371 + -1) and path5_i392 = res_i359 and path5_i414 = res_i360 and path5_i374 = res_i361 and path5_i359 = initial_i359 and path5_i360 = initial_i360 and path5_i361 = initial_i361) and (T and 0 = 0 and 0 <= path5_i369 and path5_i369 <= path5_i360 and path5_i369 <= path5_i360 and path5_i370 > 0 and path5_i370 != path5_i371 and path5_i370 < path5_i371 and path5_i374 != 0 and path5_i374 != 0 and path5_i377 = path5_i392 and path5_i392 = path5_i392)) or ((path6_i359 = path6_i369 and path6_i360 = path6_i371 and path6_i369 = path6_i370 and path6_i382 = (path6_i370 + -1) and path6_i393 = (path6_i371 - 2) and path6_i415 = (path6_i371 + -1) and path6_i393 = res_i359 and path6_i415 = res_i360 and 0 = res_i361 and path6_i359 = initial_i359 and path6_i360 = initial_i360 and path6_i361 = initial_i361) and (T and 0 = 0 and 0 <= path6_i369 and path6_i369 <= path6_i360 and path6_i369 <= path6_i360 and path6_i370 > 0 and path6_i370 != path6_i371 and path6_i370 < path6_i371 and path6_i361 = 0 and T and T and path6_i382 = path6_i393 and path6_i393 = path6_i393)) or ((path7_i359 = path7_i369 and path7_i360 = path7_i371 and path7_i369 = path7_i370 and path7_i387 = (path7_i371 + -1) and path7_i387 = path7_i382 and path7_i393 = (path7_i371 - 2) and path7_i382 = res_i359 and path7_i371 = res_i360 and 0 = res_i361 and path7_i359 = initial_i359 and path7_i360 = initial_i360 and path7_i361 = initial_i361) and (T and 0 = 0 and 0 <= path7_i369 and path7_i369 <= path7_i360 and path7_i369 <= path7_i360 and path7_i370 > 0 and path7_i370 = path7_i371 and path7_i371 = path7_i371 and T and T and path7_i382 != path7_i393 and path7_i382 != path7_i393)) or ((path9_i359 = path9_i369 and path9_i360 = path9_i373 and path9_i395 = (path9_i373 - 2) and path9_i430 = (path9_i373 + -1) and 1 = res_i359 and 1 = res_i361 and path9_i430 = res_i360 and path9_i359 = initial_i359 and path9_i360 = initial_i360 and path9_i361 = initial_i361) and (T and 0 = 0 and 0 <= path9_i369 and path9_i369 <= path9_i360 and path9_i369 <= path9_i360 and path9_i369 = 0 and T and T and 0 = 0 and 0 < path9_i373 and 1 > 0 and 1 > 0 and T and path9_i395 = 1)) or ((path10_i359 = path10_i369 and path10_i360 = path10_i371 and path10_i369 = path10_i370 and path10_i387 = (path10_i371 + -1) and path10_i387 = path10_i382 and path10_i393 = (path10_i371 - 2) and path10_i415 = (path10_i371 + -1) and path10_i393 = res_i359 and path10_i415 = res_i360 and 0 = res_i361 and path10_i359 = initial_i359 and path10_i360 = initial_i360 and path10_i361 = initial_i361) and (T and 0 = 0 and 0 <= path10_i369 and path10_i369 <= path10_i360 and path10_i369 <= path10_i360 and path10_i370 > 0 and path10_i370 = path10_i371 and path10_i371 = path10_i371 and T and T and path10_i382 = path10_i393 and path10_i393 = path10_i393)) or ((path1_i359 = path1_i369 and path1_i360 = path1_i371 and path1_i369 = path1_i370 and path1_i361 = path1_i374 and path1_i377 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i377 = res_i359 and path1_i371 = res_i360 and path1_i374 = res_i361 and path1_i359 = initial_i359 and path1_i360 = initial_i360 and path1_i361 = initial_i361) and (T and 0 = 0 and 0 <= path1_i369 and path1_i369 <= path1_i360 and path1_i369 <= path1_i360 and path1_i370 > 0 and path1_i370 < path1_i371 and path1_i374 != 0 and path1_i374 != 0 and path1_i377 != path1_i392 and path1_i377 != path1_i392 and path1_i370 < path1_i371)) or ((path1_i359 = path1_i369 and path1_i360 = path1_i371 and path1_i369 = path1_i370 and path1_i361 = path1_i374 and path1_i377 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i377 = res_i359 and path1_i371 = res_i360 and path1_i374 = res_i361 and path1_i359 = initial_i359 and path1_i360 = initial_i360 and path1_i361 = initial_i361) and (T and 0 = 0 and 0 <= path1_i369 and path1_i369 <= path1_i360 and path1_i369 <= path1_i360 and path1_i370 > 0 and path1_i370 < path1_i371 and path1_i374 != 0 and path1_i374 != 0 and path1_i377 != path1_i392 and path1_i377 != path1_i392 and path1_i370 > path1_i371)) or ((path1_i359 = path1_i369 and path1_i360 = path1_i371 and path1_i369 = path1_i370 and path1_i361 = path1_i374 and path1_i377 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i377 = res_i359 and path1_i371 = res_i360 and path1_i374 = res_i361 and path1_i359 = initial_i359 and path1_i360 = initial_i360 and path1_i361 = initial_i361) and (T and 0 = 0 and 0 <= path1_i369 and path1_i369 <= path1_i360 and path1_i369 <= path1_i360 and path1_i370 > 0 and path1_i370 != path1_i371 and path1_i370 < path1_i371 and path1_i374 != 0 and path1_i377 != path1_i392 and path1_i377 != path1_i392 and path1_i374 < 0)) or ((path1_i359 = path1_i369 and path1_i360 = path1_i371 and path1_i369 = path1_i370 and path1_i361 = path1_i374 and path1_i377 = (path1_i370 + 1) and path1_i392 = (path1_i371 - 2) and path1_i377 = res_i359 and path1_i371 = res_i360 and path1_i374 = res_i361 and path1_i359 = initial_i359 and path1_i360 = initial_i360 and path1_i361 = initial_i361) and (T and 0 = 0 and 0 <= path1_i369 and path1_i369 <= path1_i360 and path1_i369 <= path1_i360 and path1_i370 > 0 and path1_i370 != path1_i371 and path1_i370 < path1_i371 and path1_i374 != 0 and path1_i377 != path1_i392 and path1_i377 != path1_i392 and path1_i374 > 0))) and (((res1_i359 = res1_i369 and res1_i360 = res1_i371 and res1_i369 = res1_i370 and res1_i361 = res1_i374 and res1_i377 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i359 = res1_i359 and res_i360 = res1_i360 and res_i361 = res1_i361) and !(T and 0 = 0 and 0 <= res1_i369 and res1_i369 <= res1_i360 and res1_i369 <= res1_i360 and res1_i370 > 0 and res1_i370 != res1_i371 and res1_i370 < res1_i371 and res1_i374 != 0 and res1_i374 != 0 and res1_i377 != res1_i392 and res1_i377 != res1_i392)) and ((res2_i359 = res2_i369 and res2_i360 = res2_i371 and res2_i369 = res2_i370 and res2_i382 = (res2_i370 + -1) and res2_i393 = (res2_i371 - 2) and res_i359 = res2_i359 and res_i360 = res2_i360 and res_i361 = res2_i361) and !(T and 0 = 0 and 0 <= res2_i369 and res2_i369 <= res2_i360 and res2_i369 <= res2_i360 and res2_i370 > 0 and res2_i370 != res2_i371 and res2_i370 < res2_i371 and res2_i361 = 0 and T and T and res2_i382 != res2_i393 and res2_i382 != res2_i393)) and ((res3_i359 = res3_i369 and res3_i360 = res3_i373 and res3_i395 = (res3_i373 - 2) and res3_i395 = res3_i410 and res_i359 = res3_i359 and res_i360 = res3_i360 and res_i361 = res3_i361) and !(T and 0 = 0 and 0 <= res3_i369 and res3_i369 <= res3_i360 and res3_i369 <= res3_i360 and res3_i369 = 0 and T and T and 0 = 0 and 0 < res3_i373 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 > res3_i410)) and ((res4_i359 = res4_i369 and res4_i360 = res4_i373 and res4_i395 = (res4_i373 - 2) and res4_i373 = res4_i412 and res4_i395 = res4_i411 and res_i359 = res4_i359 and res_i360 = res4_i360 and res_i361 = res4_i361) and !(T and 0 = 0 and 0 <= res4_i369 and res4_i369 <= res4_i360 and res4_i369 <= res4_i360 and res4_i369 = 0 and T and T and 0 = 0 and 0 < res4_i373 and 1 > 0 and 1 > 0 and T and 1 = 1 and 1 < res4_i411)) and ((res5_i359 = res5_i369 and res5_i360 = res5_i371 and res5_i369 = res5_i370 and res5_i361 = res5_i374 and res5_i377 = (res5_i370 + 1) and res5_i392 = (res5_i371 - 2) and res5_i414 = (res5_i371 + -1) and res_i359 = res5_i359 and res_i360 = res5_i360 and res_i361 = res5_i361) and !(T and 0 = 0 and 0 <= res5_i369 and res5_i369 <= res5_i360 and res5_i369 <= res5_i360 and res5_i370 > 0 and res5_i370 != res5_i371 and res5_i370 < res5_i371 and res5_i374 != 0 and res5_i374 != 0 and res5_i377 = res5_i392 and res5_i392 = res5_i392)) and ((res6_i359 = res6_i369 and res6_i360 = res6_i371 and res6_i369 = res6_i370 and res6_i382 = (res6_i370 + -1) and res6_i393 = (res6_i371 - 2) and res6_i415 = (res6_i371 + -1) and res_i359 = res6_i359 and res_i360 = res6_i360 and res_i361 = res6_i361) and !(T and 0 = 0 and 0 <= res6_i369 and res6_i369 <= res6_i360 and res6_i369 <= res6_i360 and res6_i370 > 0 and res6_i370 != res6_i371 and res6_i370 < res6_i371 and res6_i361 = 0 and T and T and res6_i382 = res6_i393 and res6_i393 = res6_i393)) and ((res7_i359 = res7_i369 and res7_i360 = res7_i371 and res7_i369 = res7_i370 and res7_i387 = (res7_i371 + -1) and res7_i387 = res7_i382 and res7_i393 = (res7_i371 - 2) and res_i359 = res7_i359 and res_i360 = res7_i360 and res_i361 = res7_i361) and !(T and 0 = 0 and 0 <= res7_i369 and res7_i369 <= res7_i360 and res7_i369 <= res7_i360 and res7_i370 > 0 and res7_i370 = res7_i371 and res7_i371 = res7_i371 and T and T and res7_i382 != res7_i393 and res7_i382 != res7_i393)) and ((res9_i359 = res9_i369 and res9_i360 = res9_i373 and res9_i395 = (res9_i373 - 2) and res9_i430 = (res9_i373 + -1) and res_i359 = res9_i359 and res_i360 = res9_i360 and res_i361 = res9_i361) and !(T and 0 = 0 and 0 <= res9_i369 and res9_i369 <= res9_i360 and res9_i369 <= res9_i360 and res9_i369 = 0 and T and T and 0 = 0 and 0 < res9_i373 and 1 > 0 and 1 > 0 and T and res9_i395 = 1)) and ((res10_i359 = res10_i369 and res10_i360 = res10_i371 and res10_i369 = res10_i370 and res10_i387 = (res10_i371 + -1) and res10_i387 = res10_i382 and res10_i393 = (res10_i371 - 2) and res10_i415 = (res10_i371 + -1) and res_i359 = res10_i359 and res_i360 = res10_i360 and res_i361 = res10_i361) and !(T and 0 = 0 and 0 <= res10_i369 and res10_i369 <= res10_i360 and res10_i369 <= res10_i360 and res10_i370 > 0 and res10_i370 = res10_i371 and res10_i371 = res10_i371 and T and T and res10_i382 = res10_i393 and res10_i393 = res10_i393)) and ((res1_i359 = res1_i369 and res1_i360 = res1_i371 and res1_i369 = res1_i370 and res1_i361 = res1_i374 and res1_i377 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i359 = res1_i359 and res_i360 = res1_i360 and res_i361 = res1_i361) and !(T and 0 = 0 and 0 <= res1_i369 and res1_i369 <= res1_i360 and res1_i369 <= res1_i360 and res1_i370 > 0 and res1_i370 < res1_i371 and res1_i374 != 0 and res1_i374 != 0 and res1_i377 != res1_i392 and res1_i377 != res1_i392 and res1_i370 < res1_i371)) and ((res1_i359 = res1_i369 and res1_i360 = res1_i371 and res1_i369 = res1_i370 and res1_i361 = res1_i374 and res1_i377 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i359 = res1_i359 and res_i360 = res1_i360 and res_i361 = res1_i361) and !(T and 0 = 0 and 0 <= res1_i369 and res1_i369 <= res1_i360 and res1_i369 <= res1_i360 and res1_i370 > 0 and res1_i370 < res1_i371 and res1_i374 != 0 and res1_i374 != 0 and res1_i377 != res1_i392 and res1_i377 != res1_i392 and res1_i370 > res1_i371)) and ((res1_i359 = res1_i369 and res1_i360 = res1_i371 and res1_i369 = res1_i370 and res1_i361 = res1_i374 and res1_i377 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i359 = res1_i359 and res_i360 = res1_i360 and res_i361 = res1_i361) and !(T and 0 = 0 and 0 <= res1_i369 and res1_i369 <= res1_i360 and res1_i369 <= res1_i360 and res1_i370 > 0 and res1_i370 != res1_i371 and res1_i370 < res1_i371 and res1_i374 != 0 and res1_i377 != res1_i392 and res1_i377 != res1_i392 and res1_i374 < 0)) and ((res1_i359 = res1_i369 and res1_i360 = res1_i371 and res1_i369 = res1_i370 and res1_i361 = res1_i374 and res1_i377 = (res1_i370 + 1) and res1_i392 = (res1_i371 - 2) and res_i359 = res1_i359 and res_i360 = res1_i360 and res_i361 = res1_i361) and !(T and 0 = 0 and 0 <= res1_i369 and res1_i369 <= res1_i360 and res1_i369 <= res1_i360 and res1_i370 > 0 and res1_i370 != res1_i371 and res1_i370 < res1_i371 and res1_i374 != 0 and res1_i377 != res1_i392 and res1_i377 != res1_i392 and res1_i374 > 0))))) to be UNSAT. Consequently, the loop will not terminate. ---------------------------------------- (6) NO