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, 2076 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(i, j, an, bn) -> f2(x_1, j, an, bn) :|: TRUE
f2(x, x1, x2, x3) -> f3(x, x4, x2, x3) :|: TRUE
f3(x5, x6, x7, x8) -> f4(x5, x6, x9, x8) :|: TRUE
f4(x10, x11, x12, x13) -> f5(x10, x11, x12, x14) :|: TRUE
f10(x15, x16, x17, x18) -> f13(x15, arith, x17, x18) :|: TRUE && arith = x16 + 1
f11(x109, x110, x111, x112) -> f14(x113, x110, x111, x112) :|: TRUE && x113 = x109 + 1
f7(x23, x24, x25, x26) -> f10(x23, x24, x25, x26) :|: x27 < 0
f7(x114, x115, x116, x117) -> f10(x114, x115, x116, x117) :|: x118 > 0
f7(x28, x29, x30, x31) -> f11(x28, x29, x30, x31) :|: x32 = 0
f13(x33, x34, x35, x36) -> f12(x33, x34, x35, x36) :|: TRUE
f14(x37, x38, x39, x40) -> f12(x37, x38, x39, x40) :|: TRUE
f15(x119, x120, x121, x122) -> f18(x123, x120, x121, x122) :|: TRUE && x123 = x119 + 1
f19(x124, x125, x126, x127) -> f22(x124, x128, x126, x127) :|: TRUE && x128 = x125 + 1
f16(x49, x50, x51, x52) -> f19(x49, x50, x51, x52) :|: x51 <= x49 && x52 >= x50
f16(x53, x54, x55, x56) -> f20(x53, x54, x55, x56) :|: x55 > x53
f16(x129, x130, x131, x132) -> f20(x129, x130, x131, x132) :|: x132 < x130
f22(x57, x58, x59, x60) -> f21(x57, x58, x59, x60) :|: TRUE
f20(x61, x62, x63, x64) -> f21(x61, x62, x63, x64) :|: TRUE
f8(x65, x66, x67, x68) -> f15(x65, x66, x67, x68) :|: x67 >= x65 && x68 <= x66
f8(x69, x70, x71, x72) -> f16(x69, x70, x71, x72) :|: x71 < x69
f8(x133, x134, x135, x136) -> f16(x133, x134, x135, x136) :|: x136 > x134
f18(x73, x74, x75, x76) -> f17(x73, x74, x75, x76) :|: TRUE
f21(x77, x78, x79, x80) -> f17(x77, x78, x79, x80) :|: TRUE
f6(x81, x82, x83, x84) -> f7(x81, x82, x83, x84) :|: x83 >= x81 && x84 >= x82
f6(x85, x86, x87, x88) -> f8(x85, x86, x87, x88) :|: x87 < x85
f6(x137, x138, x139, x140) -> f8(x137, x138, x139, x140) :|: x140 < x138
f12(x89, x90, x91, x92) -> f9(x89, x90, x91, x92) :|: TRUE
f17(x93, x94, x95, x96) -> f9(x93, x94, x95, x96) :|: TRUE
f5(x97, x98, x99, x100) -> f6(x97, x98, x99, x100) :|: x99 <= x97 && x100 >= x98
f5(x141, x142, x143, x144) -> f6(x141, x142, x143, x144) :|: x143 >= x141 && x144 >= x142
f5(x145, x146, x147, x148) -> f6(x145, x146, x147, x148) :|: x147 >= x145 && x148 <= x146
f9(x101, x102, x103, x104) -> f5(x101, x102, x103, x104) :|: TRUE
f5(x105, x106, x107, x108) -> f23(x105, x106, x107, x108) :|: x107 < x105 && x107 < x105 && x107 > x105
f5(x149, x150, x151, x152) -> f23(x149, x150, x151, x152) :|: x151 < x149 && x151 < x149 && x152 < x150
f5(x153, x154, x155, x156) -> f23(x153, x154, x155, x156) :|: x155 < x153 && x156 > x154 && x155 > x153
f5(x157, x158, x159, x160) -> f23(x157, x158, x159, x160) :|: x159 < x157 && x160 > x158 && x160 < x158
f5(x161, x162, x163, x164) -> f23(x161, x162, x163, x164) :|: x164 < x162 && x163 < x161 && x163 > x161
f5(x165, x166, x167, x168) -> f23(x165, x166, x167, x168) :|: x168 < x166 && x167 < x165 && x168 < x166
f5(x169, x170, x171, x172) -> f23(x169, x170, x171, x172) :|: x172 < x170 && x172 > x170 && x171 > x169
f5(x173, x174, x175, x176) -> f23(x173, x174, x175, x176) :|: x176 < x174 && x176 > x174 && x176 < x174
Start term: f1(i, j, an, bn)

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

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

   (f1_4,1)
   (f2_4,2)
   (f3_4,3)
   (f4_4,4)
   (f5_4,5)
   (f10_4,6)
   (f13_4,7)
   (f11_4,8)
   (f14_4,9)
   (f7_4,10)
   (f12_4,11)
   (f15_4,12)
   (f18_4,13)
   (f19_4,14)
   (f22_4,15)
   (f16_4,16)
   (f20_4,17)
   (f21_4,18)
   (f8_4,19)
   (f17_4,20)
   (f6_4,21)
   (f9_4,22)
   (f23_4,23)

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

(4)
Obligation:
START: 1;

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

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

FROM: 3;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := nondet();
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX4;
x3 := oldX3;
TO: 4;

FROM: 4;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := nondet();
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX4;
TO: 5;

FROM: 6;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := -(-(oldX1 + 1));
assume(0 = 0 && oldX4 = oldX1 + 1);
x0 := oldX0;
x1 := -(-(oldX1 + 1));
x2 := oldX2;
x3 := oldX3;
TO: 7;

FROM: 8;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := -(-(oldX0 + 1));
assume(0 = 0 && oldX4 = oldX0 + 1);
x0 := -(-(oldX0 + 1));
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 9;

FROM: 10;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := nondet();
assume(oldX4 < 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 6;

FROM: 10;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := nondet();
assume(oldX4 > 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 6;

FROM: 10;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := -(0);
assume(oldX4 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 8;

FROM: 7;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 11;

FROM: 9;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 11;

FROM: 12;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := -(-(oldX0 + 1));
assume(0 = 0 && oldX4 = oldX0 + 1);
x0 := -(-(oldX0 + 1));
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 13;

FROM: 14;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := -(-(oldX1 + 1));
assume(0 = 0 && oldX4 = oldX1 + 1);
x0 := oldX0;
x1 := -(-(oldX1 + 1));
x2 := oldX2;
x3 := oldX3;
TO: 15;

FROM: 16;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 <= oldX0 && oldX3 >= oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 14;

FROM: 16;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 > oldX0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 17;

FROM: 16;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX3 < oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 17;

FROM: 15;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 18;

FROM: 17;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 18;

FROM: 19;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 >= oldX0 && oldX3 <= oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 12;

FROM: 19;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 < oldX0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 16;

FROM: 19;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX3 > oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 16;

FROM: 13;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 20;

FROM: 18;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 20;

FROM: 21;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 >= oldX0 && oldX3 >= oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 10;

FROM: 21;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 < oldX0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 19;

FROM: 21;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX3 < oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 19;

FROM: 11;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 22;

FROM: 20;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 22;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 <= oldX0 && oldX3 >= oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 21;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 >= oldX0 && oldX3 >= oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 21;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 >= oldX0 && oldX3 <= oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 21;

FROM: 22;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 5;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 < oldX0 && oldX2 < oldX0 && oldX2 > oldX0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 23;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 < oldX0 && oldX2 < oldX0 && oldX3 < oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 23;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 < oldX0 && oldX3 > oldX1 && oldX2 > oldX0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 23;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX2 < oldX0 && oldX3 > oldX1 && oldX3 < oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 23;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX3 < oldX1 && oldX2 < oldX0 && oldX2 > oldX0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 23;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX3 < oldX1 && oldX2 < oldX0 && oldX3 < oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 23;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX3 < oldX1 && oldX3 > oldX1 && oldX2 > oldX0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 23;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
assume(oldX3 < oldX1 && oldX3 > oldX1 && oldX3 < oldX1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
TO: 23;


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

(5) T2 (EQUIVALENT)
Initially, performed program simplifications using lexicographic rank functions:
 * Removed transitions 31, 32, 33, 34, 35, 39, 43, 46 using the following rank functions:
    - Rank function 1:
      RF for loc. 17: -2-2*x0-4*x1+2*x2+4*x3
      RF for loc. 18: 1-2*x0-4*x1+2*x2+4*x3
      RF for loc. 19: -1-2*x0-4*x1+2*x2+4*x3
      RF for loc. 20: -2*x0-4*x1+2*x2+4*x3
      RF for loc. 21: -2*x0-4*x1+2*x2+4*x3
      RF for loc. 22: -2*x0-4*x1+2*x2+4*x3
      RF for loc. 23: -2*x0-4*x1+2*x2+4*x3
      RF for loc. 24: -2*x0-4*x1+2*x2+4*x3
      RF for loc. 25: -2*x0-4*x1+2*x2+4*x3
      RF for loc. 26: -2*x0-4*x1+2*x2+4*x3
      RF for loc. 27: -2*x0-4*x1+2*x2+4*x3
      Bound for (chained) transitions 43: 0
    - Rank function 2:
      RF for loc. 17: 1-x1+x3
      RF for loc. 18: 1-x1+x3
      RF for loc. 19: 2-x1+x3
      RF for loc. 20: -x1+x3
      RF for loc. 21: -x1+x3
      RF for loc. 22: -x1+x3
      RF for loc. 23: -x1+x3
      RF for loc. 24: -x1+x3
      RF for loc. 25: -x1+x3
      RF for loc. 26: -x1+x3
      RF for loc. 27: -x1+x3
      Bound for (chained) transitions 35: 0
    - Rank function 3:
      RF for loc. 17: 2
      RF for loc. 18: 1
      RF for loc. 19: 3
      RF for loc. 20: 0
      RF for loc. 21: 0
      RF for loc. 22: 0
      RF for loc. 23: 0
      RF for loc. 24: 0
      RF for loc. 25: 0
      RF for loc. 26: 0
      RF for loc. 27: 0
      Bound for (chained) transitions 31: 2
      Bound for (chained) transitions 32: 3
      Bound for (chained) transitions 33: 3
      Bound for (chained) transitions 34: 3
      Bound for (chained) transitions 46: 1
    - Rank function 4:
      RF for loc. 20: -x0+x2
      RF for loc. 21: -x0+x2
      RF for loc. 22: -x0+x2
      RF for loc. 23: -x0+x2
      RF for loc. 24: -x0+x2
      RF for loc. 25: -x0+x2
      RF for loc. 26: -x0+x2
      RF for loc. 27: -x0+x2
      Bound for (chained) transitions 39: 0

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

(6)
YES