/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.jar /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox2/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, 96 ms] (2) JBC problem (3) JBCToGraph [EQUIVALENT, 467 ms] (4) JBCTerminationGraph (5) JBCNonTerm [COMPLETE, 1064 ms] (6) NO ---------------------------------------- (0) Obligation: need to prove termination of the following program: package simple.plait; public class Main { /** * @param args */ public static void main(String[] args) { Plait.loop(args[0].length(),args[1].length(),args[2].length()); } } package simple.plait; public class Plait { // does not terminate for ??? public static void loop(int i, int j, int k) { int plaitNext = 0; int swap = 0; while (i > 0 || j > 0 || k > 0) { if (plaitNext == 0) { swap = i; i = j/2; j = swap*2; plaitNext = 1; } else { swap = k; k = j*2; j = swap/2; plaitNext = 0; } } } } ---------------------------------------- (1) BareJBCToJBCProof (EQUIVALENT) initialized classpath ---------------------------------------- (2) Obligation: need to prove termination of the following program: package simple.plait; public class Main { /** * @param args */ public static void main(String[] args) { Plait.loop(args[0].length(),args[1].length(),args[2].length()); } } package simple.plait; public class Plait { // does not terminate for ??? public static void loop(int i, int j, int k) { int plaitNext = 0; int swap = 0; while (i > 0 || j > 0 || k > 0) { if (plaitNext == 0) { swap = i; i = j/2; j = swap*2; plaitNext = 1; } else { swap = k; k = j*2; j = swap/2; plaitNext = 0; } } } } ---------------------------------------- (3) JBCToGraph (EQUIVALENT) Constructed TerminationGraph. ---------------------------------------- (4) Obligation: Termination Graph based on JBC Program: simple.plait.Main.main([Ljava/lang/String;)V: Graph of 287 nodes with 1 SCC. ---------------------------------------- (5) JBCNonTerm (COMPLETE) Constructed a run with a repetition. States 35 and 141 are repetitions (when considering only the interesting positions [os_0_0, lv_0_2, lv_0_4]). 0: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 1: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 2: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 3: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 4: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 5: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 6: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 7: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 8: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 9: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 10: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 11: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 12: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 13: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 14: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 15: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 16: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} a34([java.lang.String...]): {o15, o37, o79} -->{java.lang.Object...} o37!: String(count=11, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} o15!: String(count=5, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} o38:: [CHAR] -->{java.lang.Object...} o16:: [CHAR] -->{java.lang.Object...} a34-><-o80 a34-><-o79 a34-><-o38 a34-><-o37 a34-><-o16 a34-><-o15 YES: (JL1) 17: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} YES: (JL1) 18: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} YES: (JL1) 19: o79!: String(count=0, hash=#, offset=[0,+inf), value=o80?) -->{java.lang.Object...} o80:: [CHAR] -->{java.lang.Object...} YES: (JL1) 20: YES: (JL1) 21: YES: (JL1) 22: YES: (JL1) 23: YES: (JL1) 24: YES: (JL1) 25: YES: (JL1) 26: YES: (JL1) 27: YES: (JL1) 28: YES: (JL1) 29: YES: (JL1) 30: YES: (JL1) 31: YES: (JL1) 32: YES: (JL1) 33: YES: (JL1) 34: YES: (JL1) 35: YES: (JL1) 36: YES: (JL1) 37: YES: (JL1) 38: YES: (JL1) 39: YES: (JL1) 40: YES: (JL1) 41: YES: (JL1) 42: YES: (JL1) 43: YES: (JL1) 44: YES: (JL1) 45: YES: (JL1) 46: YES: (JL1) 47: YES: (JL1) 48: YES: (JL1) 49: YES: (JL1) 50: YES: (JL1) 51: YES: (JL1) 52: YES: (JL1) 53: YES: (JL1) 54: YES: (JL1) 55: YES: (JL1) 56: YES: (JL1) 57: YES: (JL1) 58: YES: (JL1) 59: YES: (JL1) 60: YES: (JL1) 61: YES: (JL1) 62: YES: (JL1) 63: YES: (JL1) 64: YES: (JL1) 65: YES: (JL1) 66: YES: (JL1) 67: YES: (JL1) 68: YES: (JL1) 69: YES: (JL1) 70: YES: (JL1) 71: YES: (JL1) 72: YES: (JL1) 73: YES: (JL1) 74: YES: (JL1) 75: YES: (JL1) 76: YES: (JL1) 77: YES: (JL1) 78: YES: (JL1) 79: YES: (JL1) 80: YES: (JL1) 81: YES: (JL1) 82: YES: (JL1) 83: YES: (JL1) 84: YES: (JL1) 85: YES: (JL1) 86: YES: (JL1) 87: YES: (JL1) 88: YES: (JL1) 89: YES: (JL1) 90: YES: (JL1) 91: YES: (JL1) 92: YES: (JL1) 93: YES: (JL1) 94: YES: (JL1) 95: YES: (JL1) 96: YES: (JL1) 97: YES: (JL1) 98: YES: (JL1) 99: YES: (JL1) 100: YES: (JL1) 101: YES: (JL1) 102: YES: (JL1) 103: YES: (JL1) 104: YES: (JL1) 105: YES: (JL1) 106: YES: (JL1) 107: YES: (JL1) 108: YES: (JL1) 109: YES: (JL1) 110: YES: (JL1) 111: YES: (JL1) 112: YES: (JL1) 113: YES: (JL1) 114: YES: (JL1) 115: YES: (JL1) 116: YES: (JL1) 117: YES: (JL1) 118: YES: (JL1) 119: YES: (JL1) 120: YES: (JL1) 121: YES: (JL1) 122: YES: (JL1) 123: YES: (JL1) 124: YES: (JL1) 125: YES: (JL1) 126: YES: (JL1) 127: YES: (JL1) 128: YES: (JL1) 129: YES: (JL1) 130: YES: (JL1) 131: YES: (JL1) 132: YES: (JL1) 133: YES: (JL1) 134: YES: (JL1) 135: YES: (JL1) 136: YES: (JL1) 137: YES: (JL1) 138: YES: (JL1) 139: YES: (JL1) 140: YES: (JL1) 141: YES: (JL1) ---------------------------------------- (6) NO