10.19/3.37	YES
10.19/3.38	proof of /export/starexec/sandbox2/benchmark/theBenchmark.c
10.19/3.38	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
10.19/3.38	
10.19/3.38	
10.19/3.38	Termination of the given C Problem could be proven:
10.19/3.38	
10.19/3.38	(0) C Problem
10.19/3.38	(1) CToIRSProof [EQUIVALENT, 0 ms]
10.19/3.38	(2) IntTRS
10.19/3.38	(3) IRS2T2 [EQUIVALENT, 0 ms]
10.19/3.38	(4) T2IntSys
10.19/3.38	(5) T2 [EQUIVALENT, 1588 ms]
10.19/3.38	(6) YES
10.19/3.38	
10.19/3.38	
10.19/3.38	----------------------------------------
10.19/3.38	
10.19/3.38	(0)
10.19/3.38	Obligation:
10.19/3.38	c file /export/starexec/sandbox2/benchmark/theBenchmark.c
10.19/3.38	----------------------------------------
10.19/3.38	
10.19/3.38	(1) CToIRSProof (EQUIVALENT)
10.19/3.38	Parsed C Integer Program as IRS.
10.19/3.38	----------------------------------------
10.19/3.38	
10.19/3.38	(2)
10.19/3.38	Obligation:
10.19/3.38	Rules:
10.19/3.38	f1(x, y) -> f2(x_1, y) :|: TRUE
10.19/3.38	f2(x1, x2) -> f3(x1, x3) :|: TRUE
10.19/3.38	f4(x4, x5) -> f5(arith, x5) :|: TRUE && arith = x4 - 1
10.19/3.38	f5(x42, x43) -> f6(x42, x44) :|: TRUE && x44 = x43 + x42
10.19/3.38	f7(x45, x46) -> f8(x45, x47) :|: TRUE && x47 = x46 - 1
10.19/3.38	f9(x48, x49) -> f10(x50, x49) :|: TRUE && x50 = x48 + 1
10.19/3.38	f10(x51, x52) -> f11(x51, x53) :|: TRUE && x53 = x52 - 2
10.19/3.38	f8(x14, x15) -> f9(x14, x15) :|: x15 >= x14 + 3 && x16 < 0
10.19/3.38	f8(x54, x55) -> f9(x54, x55) :|: x55 >= x54 + 3 && x56 > 0
10.19/3.38	f11(x17, x18) -> f8(x17, x18) :|: TRUE
10.19/3.38	f8(x19, x20) -> f12(x19, x20) :|: x20 < x19 + 3
10.19/3.38	f8(x57, x58) -> f12(x57, x58) :|: x59 = 0
10.19/3.38	f12(x60, x61) -> f13(x60, x62) :|: TRUE && x62 = x61 - 1
10.19/3.38	f6(x24, x25) -> f7(x24, x25) :|: x25 >= x24 + 1 && x26 < 0
10.19/3.38	f6(x63, x64) -> f7(x63, x64) :|: x64 >= x63 + 1 && x65 > 0
10.19/3.38	f13(x27, x28) -> f6(x27, x28) :|: TRUE
10.19/3.38	f6(x29, x30) -> f14(x29, x30) :|: x30 < x29 + 1
10.19/3.38	f6(x66, x67) -> f14(x66, x67) :|: x68 = 0
10.19/3.38	f14(x69, x70) -> f15(x71, x70) :|: TRUE && x71 = x69 - 1
10.19/3.38	f15(x72, x73) -> f16(x72, x74) :|: TRUE && x74 = x73 - x72
10.19/3.38	f3(x36, x37) -> f4(x36, x37) :|: x36 >= 2
10.19/3.38	f16(x38, x39) -> f3(x38, x39) :|: TRUE
10.19/3.38	f3(x40, x41) -> f17(x40, x41) :|: x40 < 2
10.19/3.38	Start term: f1(x, y)
10.19/3.38	
10.19/3.38	----------------------------------------
10.19/3.38	
10.19/3.38	(3) IRS2T2 (EQUIVALENT)
10.19/3.38	Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs:
10.19/3.38	
10.19/3.38	   (f1_2,1)
10.19/3.38	   (f2_2,2)
10.19/3.38	   (f3_2,3)
10.19/3.38	   (f4_2,4)
10.19/3.38	   (f5_2,5)
10.19/3.38	   (f6_2,6)
10.19/3.38	   (f7_2,7)
10.19/3.38	   (f8_2,8)
10.19/3.38	   (f9_2,9)
10.19/3.38	   (f10_2,10)
10.19/3.38	   (f11_2,11)
10.19/3.38	   (f12_2,12)
10.19/3.38	   (f13_2,13)
10.19/3.38	   (f14_2,14)
10.19/3.38	   (f15_2,15)
10.19/3.38	   (f16_2,16)
10.19/3.38	   (f17_2,17)
10.19/3.38	
10.19/3.38	----------------------------------------
10.19/3.38	
10.19/3.38	(4)
10.19/3.38	Obligation:
10.19/3.38	START: 1;
10.19/3.38	
10.19/3.38	FROM: 1;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := nondet();
10.19/3.38	assume(0 = 0);
10.19/3.38	x0 := oldX2;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 2;
10.19/3.38	
10.19/3.38	FROM: 2;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := nondet();
10.19/3.38	assume(0 = 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX2;
10.19/3.38	TO: 3;
10.19/3.38	
10.19/3.38	FROM: 4;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(1 - oldX0);
10.19/3.38	assume(0 = 0 && oldX2 = oldX0 - 1);
10.19/3.38	x0 := -(1 - oldX0);
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 5;
10.19/3.38	
10.19/3.38	FROM: 5;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(-(oldX1 + oldX0));
10.19/3.38	assume(0 = 0 && oldX2 = oldX1 + oldX0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := -(-(oldX1 + oldX0));
10.19/3.38	TO: 6;
10.19/3.38	
10.19/3.38	FROM: 7;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(1 - oldX1);
10.19/3.38	assume(0 = 0 && oldX2 = oldX1 - 1);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := -(1 - oldX1);
10.19/3.38	TO: 8;
10.19/3.38	
10.19/3.38	FROM: 9;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(-(oldX0 + 1));
10.19/3.38	assume(0 = 0 && oldX2 = oldX0 + 1);
10.19/3.38	x0 := -(-(oldX0 + 1));
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 10;
10.19/3.38	
10.19/3.38	FROM: 10;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(2 - oldX1);
10.19/3.38	assume(0 = 0 && oldX2 = oldX1 - 2);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := -(2 - oldX1);
10.19/3.38	TO: 11;
10.19/3.38	
10.19/3.38	FROM: 8;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := nondet();
10.19/3.38	assume(oldX1 >= oldX0 + 3 && oldX2 < 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 9;
10.19/3.38	
10.19/3.38	FROM: 8;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := nondet();
10.19/3.38	assume(oldX1 >= oldX0 + 3 && oldX2 > 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 9;
10.19/3.38	
10.19/3.38	FROM: 11;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	assume(0 = 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 8;
10.19/3.38	
10.19/3.38	FROM: 8;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	assume(oldX1 < oldX0 + 3);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 12;
10.19/3.38	
10.19/3.38	FROM: 8;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(0);
10.19/3.38	assume(oldX2 = 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 12;
10.19/3.38	
10.19/3.38	FROM: 12;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(1 - oldX1);
10.19/3.38	assume(0 = 0 && oldX2 = oldX1 - 1);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := -(1 - oldX1);
10.19/3.38	TO: 13;
10.19/3.38	
10.19/3.38	FROM: 6;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := nondet();
10.19/3.38	assume(oldX1 >= oldX0 + 1 && oldX2 < 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 7;
10.19/3.38	
10.19/3.38	FROM: 6;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := nondet();
10.19/3.38	assume(oldX1 >= oldX0 + 1 && oldX2 > 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 7;
10.19/3.38	
10.19/3.38	FROM: 13;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	assume(0 = 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 6;
10.19/3.38	
10.19/3.38	FROM: 6;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	assume(oldX1 < oldX0 + 1);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 14;
10.19/3.38	
10.19/3.38	FROM: 6;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(0);
10.19/3.38	assume(oldX2 = 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 14;
10.19/3.38	
10.19/3.38	FROM: 14;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(1 - oldX0);
10.19/3.38	assume(0 = 0 && oldX2 = oldX0 - 1);
10.19/3.38	x0 := -(1 - oldX0);
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 15;
10.19/3.38	
10.19/3.38	FROM: 15;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	oldX2 := -(oldX0 - oldX1);
10.19/3.38	assume(0 = 0 && oldX2 = oldX1 - oldX0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := -(oldX0 - oldX1);
10.19/3.38	TO: 16;
10.19/3.38	
10.19/3.38	FROM: 3;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	assume(oldX0 >= 2);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 4;
10.19/3.38	
10.19/3.38	FROM: 16;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	assume(0 = 0);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 3;
10.19/3.38	
10.19/3.38	FROM: 3;
10.19/3.38	oldX0 := x0;
10.19/3.38	oldX1 := x1;
10.19/3.38	assume(oldX0 < 2);
10.19/3.38	x0 := oldX0;
10.19/3.38	x1 := oldX1;
10.19/3.38	TO: 17;
10.19/3.38	
10.19/3.38	
10.19/3.38	----------------------------------------
10.19/3.38	
10.19/3.38	(5) T2 (EQUIVALENT)
10.19/3.38	Initially, performed program simplifications using lexicographic rank functions:
10.19/3.38	 * Removed transitions 8, 9, 10, 13, 14, 15, 16, 28, 29, 32, 33, 34, 35, 47, 48, 51, 52 using the following rank functions:
10.19/3.38	    - Rank function 1:
10.19/3.38	      RF for loc. 13: -2+5*x1
10.19/3.38	      RF for loc. 14: 1+5*x1
10.19/3.38	      RF for loc. 15: -1+5*x1
10.19/3.38	      RF for loc. 16: -3+5*x1
10.19/3.38	      RF for loc. 17: 5*x1
10.19/3.38	      RF for loc. 18: 5*x1
10.19/3.38	      RF for loc. 19: -1+5*x1
10.19/3.38	      RF for loc. 23: 5*x1
10.19/3.38	      RF for loc. 27: -1+5*x0+5*x1
10.19/3.38	      Bound for (chained) transitions 32: 10
10.19/3.38	    - Rank function 2:
10.19/3.38	      RF for loc. 13: 3+3*x0+3*x1
10.19/3.38	      RF for loc. 14: 5+3*x0+3*x1
10.19/3.38	      RF for loc. 15: 3+3*x0+3*x1
10.19/3.38	      RF for loc. 16: 2+3*x0+3*x1
10.19/3.38	      RF for loc. 17: 5+3*x0+3*x1
10.19/3.38	      RF for loc. 18: -2+3*x0+3*x1
10.19/3.38	      RF for loc. 19: 4+3*x0+3*x1
10.19/3.38	      RF for loc. 23: 4+3*x0+3*x1
10.19/3.38	      RF for loc. 27: 6*x0+3*x1
10.19/3.38	      Bound for (chained) transitions 13: 19
10.19/3.38	      Bound for (chained) transitions 14: 19
10.19/3.38	      Bound for (chained) transitions 33: 13
10.19/3.38	    - Rank function 3:
10.19/3.38	      RF for loc. 13: 3*oldX0+3*x0
10.19/3.38	      RF for loc. 14: 2+3*x0
10.19/3.38	      RF for loc. 15: 9*x0
10.19/3.38	      RF for loc. 16: oldX0+2*x0
10.19/3.38	      RF for loc. 17: 2*x0
10.19/3.38	      RF for loc. 18: -2+2*x0
10.19/3.38	      RF for loc. 19: 1+3*x0
10.19/3.38	      RF for loc. 23: -1+2*x0
10.19/3.38	      RF for loc. 27: -1+2*x0
10.19/3.38	      Bound for (chained) transitions 8: 6
10.19/3.38	      Bound for (chained) transitions 9: 9
10.19/3.38	      Bound for (chained) transitions 15: 4
10.19/3.38	      Bound for (chained) transitions 16: 4
10.19/3.38	      Bound for (chained) transitions 28: 3
10.19/3.38	      Bound for (chained) transitions 34: 1
10.19/3.38	      Bound for (chained) transitions 35: 1
10.19/3.38	      Bound for (chained) transitions 47, 48: 0
10.19/3.38	      Bound for (chained) transitions 51: 3
10.19/3.38	      Bound for (chained) transitions 52: 3
10.19/3.38	    - Rank function 4:
10.19/3.38	      RF for loc. 14: 1
10.19/3.38	      RF for loc. 17: 0
10.19/3.38	      RF for loc. 19: 0
10.19/3.38	      RF for loc. 23: -1
10.19/3.38	      Bound for (chained) transitions 10: 1
10.19/3.38	      Bound for (chained) transitions 29: 0
10.19/3.38	
10.19/3.38	----------------------------------------
10.19/3.38	
10.19/3.38	(6)
10.19/3.38	YES
10.19/3.41	EOF