5.20/2.29 NO 5.49/2.35 proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar 5.49/2.35 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.49/2.35 5.49/2.35 5.49/2.35 termination of the given Bare JBC problem could be disproven: 5.49/2.35 5.49/2.35 (0) Bare JBC problem 5.49/2.35 (1) BareJBCToJBCProof [EQUIVALENT, 96 ms] 5.49/2.35 (2) JBC problem 5.49/2.35 (3) JBCNonTerm [COMPLETE, 401 ms] 5.49/2.35 (4) NO 5.49/2.35 5.49/2.35 5.49/2.35 ---------------------------------------- 5.49/2.35 5.49/2.35 (0) 5.49/2.35 Obligation: 5.49/2.35 need to prove termination of the following program: 5.49/2.35 package simple.flip2; 5.49/2.35 5.49/2.35 public class Flip { 5.49/2.35 5.49/2.35 /* inspired by this example: 5.49/2.35 * http://www.lri.fr/~marche/termination-competition/2006/webform.cgi?command=viewpb&id=TRS.HM.n007.trs 5.49/2.35 * (VAR x y) 5.49/2.35 (RULES 5.49/2.35 f(x,y) -> f(x,x) 5.49/2.35 f(s(x),y) -> f(y,x) 5.49/2.35 ) 5.49/2.35 (COMMENT 5.49/2.35 Non-terminating. 5.49/2.35 ) 5.49/2.35 */ 5.49/2.35 5.49/2.35 public static void flip(int i, int j) { 5.49/2.35 int t = 0; 5.49/2.35 while (i > 0 && j > 0) { 5.49/2.35 if (i < j) { 5.49/2.35 t = i; 5.49/2.35 i = j; 5.49/2.35 j = t; 5.49/2.35 } else { 5.49/2.35 if (i > j) { 5.49/2.35 j = i; 5.49/2.35 } else { 5.49/2.35 i--; 5.49/2.35 } 5.49/2.35 } 5.49/2.35 } 5.49/2.35 } 5.49/2.35 } 5.49/2.35 5.49/2.35 5.49/2.35 package simple.flip2; 5.49/2.35 5.49/2.35 public class Main { 5.49/2.35 5.49/2.35 /** 5.49/2.35 * @param args 5.49/2.35 */ 5.49/2.35 public static void main(String[] args) { 5.49/2.35 Flip.flip(args[0].length(),args[1].length()); 5.49/2.35 5.49/2.35 } 5.49/2.35 5.49/2.35 } 5.49/2.35 5.49/2.35 5.49/2.35 5.49/2.35 ---------------------------------------- 5.49/2.35 5.49/2.35 (1) BareJBCToJBCProof (EQUIVALENT) 5.49/2.35 initialized classpath 5.49/2.35 ---------------------------------------- 5.49/2.35 5.49/2.35 (2) 5.49/2.35 Obligation: 5.49/2.35 need to prove termination of the following program: 5.49/2.35 package simple.flip2; 5.49/2.35 5.49/2.35 public class Flip { 5.49/2.35 5.49/2.35 /* inspired by this example: 5.49/2.35 * http://www.lri.fr/~marche/termination-competition/2006/webform.cgi?command=viewpb&id=TRS.HM.n007.trs 5.49/2.35 * (VAR x y) 5.49/2.35 (RULES 5.49/2.35 f(x,y) -> f(x,x) 5.49/2.35 f(s(x),y) -> f(y,x) 5.49/2.35 ) 5.49/2.35 (COMMENT 5.49/2.35 Non-terminating. 5.49/2.35 ) 5.49/2.35 */ 5.49/2.35 5.49/2.35 public static void flip(int i, int j) { 5.49/2.35 int t = 0; 5.49/2.35 while (i > 0 && j > 0) { 5.49/2.35 if (i < j) { 5.49/2.35 t = i; 5.49/2.35 i = j; 5.49/2.35 j = t; 5.49/2.35 } else { 5.49/2.35 if (i > j) { 5.49/2.35 j = i; 5.49/2.35 } else { 5.49/2.35 i--; 5.49/2.35 } 5.49/2.35 } 5.49/2.35 } 5.49/2.35 } 5.49/2.35 } 5.49/2.35 5.49/2.35 5.49/2.35 package simple.flip2; 5.49/2.35 5.49/2.35 public class Main { 5.49/2.35 5.49/2.35 /** 5.49/2.35 * @param args 5.49/2.35 */ 5.49/2.35 public static void main(String[] args) { 5.49/2.35 Flip.flip(args[0].length(),args[1].length()); 5.49/2.35 5.49/2.35 } 5.49/2.35 5.49/2.35 } 5.49/2.35 5.49/2.35 5.49/2.35 5.49/2.35 ---------------------------------------- 5.49/2.35 5.49/2.35 (3) JBCNonTerm (COMPLETE) 5.49/2.35 Constructed a run with a repetition. States 17 and 56 are repetitions (when considering only the interesting positions [lv_0_0, lv_0_1]). 5.49/2.35 5.49/2.35 0: 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 1: 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 2: 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 3: 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 4: 5.49/2.35 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 5: 5.49/2.35 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 6: 5.49/2.35 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 7: 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 8: 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 9: 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 a2([java.lang.String...]): {o15, o37} -->{java.lang.Object...} 5.49/2.35 o15!: String(count=3, hash=#, offset=[0,+inf), value=o16?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 o16:: [CHAR] -->{java.lang.Object...} 5.49/2.35 a2-><-o38 5.49/2.35 a2-><-o37 5.49/2.35 a2-><-o16 5.49/2.35 a2-><-o15 5.49/2.35 YES: (JL1) 5.49/2.35 10: 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 YES: (JL1) 5.49/2.35 11: 5.49/2.35 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 YES: (JL1) 5.49/2.35 12: 5.49/2.35 5.49/2.35 o37!: String(count=3, hash=#, offset=[0,+inf), value=o38?) -->{java.lang.Object...} 5.49/2.35 o38:: [CHAR] -->{java.lang.Object...} 5.49/2.35 YES: (JL1) 5.49/2.35 13: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 14: 5.49/2.35 YES: (JL1) 5.49/2.35 15: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 16: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 17: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 18: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 19: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 20: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 21: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 22: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 23: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 24: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 25: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 26: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 27: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 28: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 29: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 30: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 31: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 32: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 33: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 34: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 35: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 36: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 37: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 38: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 39: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 40: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 41: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 42: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 43: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 44: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 45: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 46: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 47: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 48: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 49: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 50: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 51: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 52: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 53: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 54: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 55: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 56: 5.49/2.35 5.49/2.35 YES: (JL1) 5.49/2.35 5.49/2.35 ---------------------------------------- 5.49/2.35 5.49/2.35 (4) 5.49/2.35 NO 5.49/2.37 EOF