YES
proof of /export/starexec/sandbox2/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, 83 ms]
(2) IntTRS
(3) IRS2T2 [EQUIVALENT, 0 ms]
(4) T2IntSys
(5) T2 [EQUIVALENT, 1866 ms]
(6) YES


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

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

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

(2)
Obligation:
Rules:
f1(N, x, y, i, r) -> f2(10, x, y, i, r) :|: TRUE
f2(x1, x2, x3, x4, x5) -> f3(x1, 0, x3, x4, x5) :|: TRUE
f3(x6, x7, x8, x9, x10) -> f4(x6, x7, 0, x9, x10) :|: TRUE
f4(x11, x12, x13, x14, x15) -> f5(x11, x12, x13, 0, x15) :|: TRUE
f6(x16, x17, x18, x19, x20) -> f7(x16, x17, x18, arith, x20) :|: TRUE && arith = x19 + 1
f7(x21, x22, x23, x24, x25) -> f8(x21, x22, x23, x24, x26) :|: TRUE
f12(x162, x163, x164, x165, x166) -> f15(x162, x167, x164, x165, x166) :|: TRUE && x167 = x163 + 1
f16(x168, x169, x170, x171, x172) -> f19(x168, x173, x170, x171, x172) :|: TRUE && x173 = x169 - 1
f20(x174, x175, x176, x177, x178) -> f23(x174, x175, x179, x177, x178) :|: TRUE && x179 = x176 + 1
f24(x180, x181, x182, x183, x184) -> f27(x180, x181, x185, x183, x184) :|: TRUE && x185 = x182 - 1
f21(x47, x48, x49, x50, x51) -> f24(x47, x48, x49, x50, x51) :|: x51 = 3
f21(x52, x53, x54, x55, x56) -> f25(x52, x53, x54, x55, x56) :|: x56 < 3
f21(x186, x187, x188, x189, x190) -> f25(x186, x187, x188, x189, x190) :|: x190 > 3
f27(x57, x58, x59, x60, x61) -> f26(x57, x58, x59, x60, x61) :|: TRUE
f25(x62, x63, x64, x65, x66) -> f26(x62, x63, x64, x65, x66) :|: TRUE
f17(x67, x68, x69, x70, x71) -> f20(x67, x68, x69, x70, x71) :|: x71 = 2
f17(x72, x73, x74, x75, x76) -> f21(x72, x73, x74, x75, x76) :|: x76 < 2
f17(x191, x192, x193, x194, x195) -> f21(x191, x192, x193, x194, x195) :|: x195 > 2
f23(x77, x78, x79, x80, x81) -> f22(x77, x78, x79, x80, x81) :|: TRUE
f26(x82, x83, x84, x85, x86) -> f22(x82, x83, x84, x85, x86) :|: TRUE
f13(x87, x88, x89, x90, x91) -> f16(x87, x88, x89, x90, x91) :|: x91 = 1
f13(x92, x93, x94, x95, x96) -> f17(x92, x93, x94, x95, x96) :|: x96 < 1
f13(x196, x197, x198, x199, x200) -> f17(x196, x197, x198, x199, x200) :|: x200 > 1
f19(x97, x98, x99, x100, x101) -> f18(x97, x98, x99, x100, x101) :|: TRUE
f22(x102, x103, x104, x105, x106) -> f18(x102, x103, x104, x105, x106) :|: TRUE
f9(x107, x108, x109, x110, x111) -> f12(x107, x108, x109, x110, x111) :|: x111 = 0
f9(x112, x113, x114, x115, x116) -> f13(x112, x113, x114, x115, x116) :|: x116 < 0
f9(x201, x202, x203, x204, x205) -> f13(x201, x202, x203, x204, x205) :|: x205 > 0
f15(x117, x118, x119, x120, x121) -> f14(x117, x118, x119, x120, x121) :|: TRUE
f18(x122, x123, x124, x125, x126) -> f14(x122, x123, x124, x125, x126) :|: TRUE
f8(x127, x128, x129, x130, x131) -> f9(x127, x128, x129, x130, x131) :|: x131 >= 0 && x131 <= 3
f8(x132, x133, x134, x135, x136) -> f10(x132, x133, x134, x135, x136) :|: x136 < 0
f8(x206, x207, x208, x209, x210) -> f10(x206, x207, x208, x209, x210) :|: x210 > 3
f14(x137, x138, x139, x140, x141) -> f11(x137, x138, x139, x140, x141) :|: TRUE
f10(x142, x143, x144, x145, x146) -> f11(x142, x143, x144, x145, x146) :|: TRUE
f5(x147, x148, x149, x150, x151) -> f6(x147, x148, x149, x150, x151) :|: x150 < x147
f11(x152, x153, x154, x155, x156) -> f5(x152, x153, x154, x155, x156) :|: TRUE
f5(x157, x158, x159, x160, x161) -> f28(x157, x158, x159, x160, x161) :|: x160 >= x157
Start term: f1(N, x, y, i, r)

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

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

   (f1_5,1)
   (f2_5,2)
   (f3_5,3)
   (f4_5,4)
   (f5_5,5)
   (f6_5,6)
   (f7_5,7)
   (f8_5,8)
   (f12_5,9)
   (f15_5,10)
   (f16_5,11)
   (f19_5,12)
   (f20_5,13)
   (f23_5,14)
   (f24_5,15)
   (f27_5,16)
   (f21_5,17)
   (f25_5,18)
   (f26_5,19)
   (f17_5,20)
   (f22_5,21)
   (f13_5,22)
   (f18_5,23)
   (f9_5,24)
   (f14_5,25)
   (f10_5,26)
   (f11_5,27)
   (f28_5,28)

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

(4)
Obligation:
START: 1;

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

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

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

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

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

FROM: 7;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
oldX5 := nondet();
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX5;
TO: 8;

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

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

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

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

FROM: 17;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 = 3);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 15;

FROM: 17;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 < 3);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 18;

FROM: 17;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 > 3);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 18;

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

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

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

FROM: 20;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 < 2);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 17;

FROM: 20;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 > 2);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 17;

FROM: 14;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 21;

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

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

FROM: 22;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 < 1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 20;

FROM: 22;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 > 1);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 20;

FROM: 12;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 23;

FROM: 21;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 23;

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

FROM: 24;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 < 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 22;

FROM: 24;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 > 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 22;

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

FROM: 23;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 25;

FROM: 8;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 >= 0 && oldX4 <= 3);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 24;

FROM: 8;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 < 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 26;

FROM: 8;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX4 > 3);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 26;

FROM: 25;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 27;

FROM: 26;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(0 = 0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 27;

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX3 < oldX0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 6;

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

FROM: 5;
oldX0 := x0;
oldX1 := x1;
oldX2 := x2;
oldX3 := x3;
oldX4 := x4;
assume(oldX3 >= oldX0);
x0 := oldX0;
x1 := oldX1;
x2 := oldX2;
x3 := oldX3;
x4 := oldX4;
TO: 28;


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

(5) T2 (EQUIVALENT)
Initially, performed program simplifications using lexicographic rank functions:
 * Removed transitions 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 50, 51, 54 using the following rank functions:
    - Rank function 1:
      RF for loc. 19: -8+15*x0-15*x3
      RF for loc. 20: -10+15*x0-15*x3
      RF for loc. 21: -9+15*x0-15*x3
      RF for loc. 22: -7+15*x0-15*x3
      RF for loc. 23: -11+15*x0-15*x3
      RF for loc. 24: -6+15*x0-15*x3
      RF for loc. 25: -12+15*x0-15*x3
      RF for loc. 26: -1+15*x0-15*x3
      RF for loc. 27: -13+15*x0-15*x3
      RF for loc. 28: 15*x0-15*x3
      RF for loc. 29: 15*x0-15*x3
      RF for loc. 30: -13+15*x0-15*x3
      RF for loc. 31: -14+15*x0-15*x3
      Bound for (chained) transitions 50: 1
      Bound for (chained) transitions 51: 1
    - Rank function 2:
      RF for loc. 19: 7+x3
      RF for loc. 20: 3+x3
      RF for loc. 21: 6+x3
      RF for loc. 22: 8+x3
      RF for loc. 23: 2+x3
      RF for loc. 24: 9+x3
      RF for loc. 25: 1+x3
      RF for loc. 26: oldX3+x3+9*x4
      RF for loc. 27: x3
      RF for loc. 28: 28*oldX3+2*x3
      RF for loc. 29: x3
      RF for loc. 30: 0
      RF for loc. 31: -1
      Bound for (chained) transitions 26: 8
      Bound for (chained) transitions 27: 8
      Bound for (chained) transitions 28: 8
      Bound for (chained) transitions 29: 7
      Bound for (chained) transitions 30: 9
      Bound for (chained) transitions 31: 9
      Bound for (chained) transitions 32: 9
      Bound for (chained) transitions 33: 4
      Bound for (chained) transitions 34: 10
      Bound for (chained) transitions 35: 10
      Bound for (chained) transitions 36: 10
      Bound for (chained) transitions 37: 3
      Bound for (chained) transitions 38: 2
      Bound for (chained) transitions 39: 2
      Bound for (chained) transitions 40: 2
      Bound for (chained) transitions 41: 2
      Bound for (chained) transitions 42: 30
      Bound for (chained) transitions 43: 30
      Bound for (chained) transitions 44: 30
      Bound for (chained) transitions 45: 1
      Bound for (chained) transitions 46: 1
      Bound for (chained) transitions 47, 54: 0

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

(6)
YES