YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.c
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination of the given C Problem could be proven:

(0) C Problem
(1) CToIRSProof [EQUIVALENT, 0 ms]
(2) IntTRS
(3) IRS2T2 [EQUIVALENT, 0 ms]
(4) T2IntSys
(5) T2 [EQUIVALENT, 1636 ms]
(6) YES


----------------------------------------

(0)
Obligation:
c file /export/starexec/sandbox/benchmark/theBenchmark.c
----------------------------------------

(1) CToIRSProof (EQUIVALENT)
Parsed C Integer Program as IRS.
----------------------------------------

(2)
Obligation:
Rules:
f1(x, y) -> f2(x_1, y) :|: TRUE
f2(x1, x2) -> f3(x1, x3) :|: TRUE
f4(x4, x5) -> f5(arith, x5) :|: TRUE && arith = x4 - 1
f5(x42, x43) -> f6(x42, x44) :|: TRUE && x44 = x43 + x42
f7(x45, x46) -> f8(x45, x47) :|: TRUE && x47 = x46 - 1
f9(x48, x49) -> f10(x50, x49) :|: TRUE && x50 = x48 + 1
f10(x51, x52) -> f11(x51, x53) :|: TRUE && x53 = x52 - 2
f8(x14, x15) -> f9(x14, x15) :|: x15 >= x14 + 3 && x16 < 0
f8(x54, x55) -> f9(x54, x55) :|: x55 >= x54 + 3 && x56 > 0
f11(x17, x18) -> f8(x17, x18) :|: TRUE
f8(x19, x20) -> f12(x19, x20) :|: x20 < x19 + 3
f8(x57, x58) -> f12(x57, x58) :|: x59 = 0
f12(x60, x61) -> f13(x60, x62) :|: TRUE && x62 = x61 - 1
f6(x24, x25) -> f7(x24, x25) :|: x25 >= x24 + 1 && x26 < 0
f6(x63, x64) -> f7(x63, x64) :|: x64 >= x63 + 1 && x65 > 0
f13(x27, x28) -> f6(x27, x28) :|: TRUE
f6(x29, x30) -> f14(x29, x30) :|: x30 < x29 + 1
f6(x66, x67) -> f14(x66, x67) :|: x68 = 0
f14(x69, x70) -> f15(x71, x70) :|: TRUE && x71 = x69 - 1
f15(x72, x73) -> f16(x72, x74) :|: TRUE && x74 = x73 - x72
f3(x36, x37) -> f4(x36, x37) :|: x36 >= 2
f16(x38, x39) -> f3(x38, x39) :|: TRUE
f3(x40, x41) -> f17(x40, x41) :|: x40 < 2
Start term: f1(x, y)

----------------------------------------

(3) IRS2T2 (EQUIVALENT)
Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs:

   (f1_2,1)
   (f2_2,2)
   (f3_2,3)
   (f4_2,4)
   (f5_2,5)
   (f6_2,6)
   (f7_2,7)
   (f8_2,8)
   (f9_2,9)
   (f10_2,10)
   (f11_2,11)
   (f12_2,12)
   (f13_2,13)
   (f14_2,14)
   (f15_2,15)
   (f16_2,16)
   (f17_2,17)

----------------------------------------

(4)
Obligation:
START: 1;

FROM: 1;
oldX0 := x0;
oldX1 := x1;
oldX2 := nondet();
assume(0 = 0);
x0 := oldX2;
x1 := oldX1;
TO: 2;

FROM: 2;
oldX0 := x0;
oldX1 := x1;
oldX2 := nondet();
assume(0 = 0);
x0 := oldX0;
x1 := oldX2;
TO: 3;

FROM: 4;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(1 - oldX0);
assume(0 = 0 && oldX2 = oldX0 - 1);
x0 := -(1 - oldX0);
x1 := oldX1;
TO: 5;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(-(oldX1 + oldX0));
assume(0 = 0 && oldX2 = oldX1 + oldX0);
x0 := oldX0;
x1 := -(-(oldX1 + oldX0));
TO: 6;

FROM: 7;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(1 - oldX1);
assume(0 = 0 && oldX2 = oldX1 - 1);
x0 := oldX0;
x1 := -(1 - oldX1);
TO: 8;

FROM: 9;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(-(oldX0 + 1));
assume(0 = 0 && oldX2 = oldX0 + 1);
x0 := -(-(oldX0 + 1));
x1 := oldX1;
TO: 10;

FROM: 10;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(2 - oldX1);
assume(0 = 0 && oldX2 = oldX1 - 2);
x0 := oldX0;
x1 := -(2 - oldX1);
TO: 11;

FROM: 8;
oldX0 := x0;
oldX1 := x1;
oldX2 := nondet();
assume(oldX1 >= oldX0 + 3 && oldX2 < 0);
x0 := oldX0;
x1 := oldX1;
TO: 9;

FROM: 8;
oldX0 := x0;
oldX1 := x1;
oldX2 := nondet();
assume(oldX1 >= oldX0 + 3 && oldX2 > 0);
x0 := oldX0;
x1 := oldX1;
TO: 9;

FROM: 11;
oldX0 := x0;
oldX1 := x1;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
TO: 8;

FROM: 8;
oldX0 := x0;
oldX1 := x1;
assume(oldX1 < oldX0 + 3);
x0 := oldX0;
x1 := oldX1;
TO: 12;

FROM: 8;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(0);
assume(oldX2 = 0);
x0 := oldX0;
x1 := oldX1;
TO: 12;

FROM: 12;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(1 - oldX1);
assume(0 = 0 && oldX2 = oldX1 - 1);
x0 := oldX0;
x1 := -(1 - oldX1);
TO: 13;

FROM: 6;
oldX0 := x0;
oldX1 := x1;
oldX2 := nondet();
assume(oldX1 >= oldX0 + 1 && oldX2 < 0);
x0 := oldX0;
x1 := oldX1;
TO: 7;

FROM: 6;
oldX0 := x0;
oldX1 := x1;
oldX2 := nondet();
assume(oldX1 >= oldX0 + 1 && oldX2 > 0);
x0 := oldX0;
x1 := oldX1;
TO: 7;

FROM: 13;
oldX0 := x0;
oldX1 := x1;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
TO: 6;

FROM: 6;
oldX0 := x0;
oldX1 := x1;
assume(oldX1 < oldX0 + 1);
x0 := oldX0;
x1 := oldX1;
TO: 14;

FROM: 6;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(0);
assume(oldX2 = 0);
x0 := oldX0;
x1 := oldX1;
TO: 14;

FROM: 14;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(1 - oldX0);
assume(0 = 0 && oldX2 = oldX0 - 1);
x0 := -(1 - oldX0);
x1 := oldX1;
TO: 15;

FROM: 15;
oldX0 := x0;
oldX1 := x1;
oldX2 := -(oldX0 - oldX1);
assume(0 = 0 && oldX2 = oldX1 - oldX0);
x0 := oldX0;
x1 := -(oldX0 - oldX1);
TO: 16;

FROM: 3;
oldX0 := x0;
oldX1 := x1;
assume(oldX0 >= 2);
x0 := oldX0;
x1 := oldX1;
TO: 4;

FROM: 16;
oldX0 := x0;
oldX1 := x1;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
TO: 3;

FROM: 3;
oldX0 := x0;
oldX1 := x1;
assume(oldX0 < 2);
x0 := oldX0;
x1 := oldX1;
TO: 17;


----------------------------------------

(5) T2 (EQUIVALENT)
Initially, performed program simplifications using lexicographic rank functions:
 * Removed transitions 8, 9, 10, 13, 14, 15, 16, 28, 29, 32, 33, 34, 35, 47, 48, 51, 52 using the following rank functions:
    - Rank function 1:
      RF for loc. 13: -2+5*x1
      RF for loc. 14: 1+5*x1
      RF for loc. 15: -1+5*x1
      RF for loc. 16: -3+5*x1
      RF for loc. 17: 5*x1
      RF for loc. 18: 5*x1
      RF for loc. 19: -1+5*x1
      RF for loc. 23: 5*x1
      RF for loc. 27: -1+5*x0+5*x1
      Bound for (chained) transitions 32: 10
    - Rank function 2:
      RF for loc. 13: 3+3*x0+3*x1
      RF for loc. 14: 5+3*x0+3*x1
      RF for loc. 15: 3+3*x0+3*x1
      RF for loc. 16: 2+3*x0+3*x1
      RF for loc. 17: 5+3*x0+3*x1
      RF for loc. 18: -2+3*x0+3*x1
      RF for loc. 19: 4+3*x0+3*x1
      RF for loc. 23: 4+3*x0+3*x1
      RF for loc. 27: 6*x0+3*x1
      Bound for (chained) transitions 13: 19
      Bound for (chained) transitions 14: 19
      Bound for (chained) transitions 33: 13
    - Rank function 3:
      RF for loc. 13: 6*oldX0+5*x0
      RF for loc. 14: 5+5*x0
      RF for loc. 15: 11*oldX0+5*x0
      RF for loc. 16: 3+oldX0+4*x0
      RF for loc. 17: 3+4*x0
      RF for loc. 18: -1+4*x0
      RF for loc. 19: 4+5*x0
      RF for loc. 23: 1+4*x0
      RF for loc. 27: 1+4*x0
      Bound for (chained) transitions 8: 11
      Bound for (chained) transitions 9: 16
      Bound for (chained) transitions 15: 9
      Bound for (chained) transitions 16: 9
      Bound for (chained) transitions 28: 8
      Bound for (chained) transitions 34: 5
      Bound for (chained) transitions 35: 5
      Bound for (chained) transitions 47, 48: 3
      Bound for (chained) transitions 51: 9
      Bound for (chained) transitions 52: 9
    - Rank function 4:
      RF for loc. 14: 1
      RF for loc. 17: 0
      RF for loc. 19: 0
      RF for loc. 23: -1
      Bound for (chained) transitions 10: 1
      Bound for (chained) transitions 29: 0

----------------------------------------

(6)
YES