/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.jar /export/starexec/sandbox2/output/output_files


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


MAYBE
proof of /export/starexec/sandbox2/benchmark/theBenchmark.jar
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


termination of the given Bare JBC problem could not be shown:

(0) Bare JBC problem
(1) BareJBCToJBCProof [EQUIVALENT, 96 ms]
(2) JBC problem


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

(0)
Obligation:
need to prove termination of the following program:
public class EquationSystem {
    private Rational A[][];
    private Rational b[];
    private int n;

    public EquationSystem(Rational A[][], Rational b[]) {
	this.n = A.length;
	this.A = new Rational[n][n];
	this.b = new Rational[n];	
	for (int l = 0; l < n; l++) {
	    for (int c = 0; c < n; c++)
		this.A[l][c] = A[l][c]; 
	    this.b[l] = b[l];
	}
    }

    /*
    public void resolve() {
	if (diagonalize()) {
	    System.out.print("One solution = ");
	    System.out.print("(");
	    for (int l = 0; l < n; l++) {
		System.out.print(b[l]);
		if (l < n-1) System.out.print("; ");
	    }
	    System.out.println(").");
	}
	else System.out.println("Zero or an infinite number of solutions.");
    }
    */

    private int searchRow(int col) {
	for (int l = col; l < n; l++)
	    if (!A[l][col].isZero()) return l;
	return n;
    }

    private void permute(int l1, int l2) {
	Rational temp;
	for (int col = l1; col < n; col++) {
	    temp = A[l1][col];
	    A[l1][col] = A[l2][col]; 
	    A[l2][col] = temp;
	}
	temp = b[l1];
	b[l1] = b[l2];
	b[l2] = temp;
    }

    private void divide(int l, Rational pivot) {
	for (int col = l; col < n; col++) A[l][col].divideBy(pivot);
	b[l].divideBy(pivot);
    }

    private void substract(int i, int j) {
	Rational A_ji = new Rational(A[j][i]);
	for (int col = i; col < n; col++)
	    A[j][col].minus(A_ji.times(A[i][col]));
	b[j].minus(A_ji.times(b[i]));
    }

    public boolean diagonalize() {
	int current;
	Rational p;
	
	for (int l = 0; l < n; l++) {
	    current = searchRow(l);
	    if (current == n) return false;
	    p = new Rational(A[current][l]);
	    permute(l, current);
	    divide(l, p);
	    for (int ll = 0; ll < n; ll++)
		if (ll != l) substract(l, ll);
	}
	
	return true;
    }

    /*
    public String toString() {
	String res = "";
	for (int l = 0; l < n; l++) {
	    for (int col = 0; col < n-1; col++)
		res += A[l][col] + "*X" + col + " + ";
	    res += A[l][n-1] + "*X" + (n-1) + " = " + b[l] + "\n";
	}
	return res;
    }
    */

    public static void main (String args[]) {
	if (args.length >= 4) {
	    Rational A[][] = new Rational[1][1];
	    Rational b[]   = new Rational[1];
	    
	    A[0][0] = new Rational(args[0].length(), args[1].length());
	    b[0] = new Rational(args[2].length(), args[3].length());
	    
	    EquationSystem S = new EquationSystem(A, b);
	    // System.out.println(S);
	    // S.resolve();
	    S.diagonalize();
	}
    }
}


public class Rational {
    private int n, d;

    public Rational() {
	n = 0; d = 1;
    }

    public Rational(int num, int den) { 
	n = num; d = den;
    }

    public Rational(Rational r) {
	n = r.n; d = r.d;
    }

    public void minus(Rational r) {
	n = n*r.d - r.n*d;
	d *= r.d;
	simplify();
    }

    public Rational times(Rational r) {
	Rational result = new Rational(n*r.n, d*r.d);
	result.simplify();
	return result;
    }

    public void divideBy(Rational r) {
	n *= r.d; 
	d *= r.n;
	simplify();
    }

    private static void eratosthene(boolean T[]) {  
	for (int i = 0; i < T.length; i++) T[i] = false;
	if (T.length  <= 4) return;
	int number = 1;
	while (number*number < T.length) {
	    while ( T[++number] && number < T.length ) {};
	    for (int i = 2*number; i < T.length; i += number)
		T[i] = true;
	}
    }

    private static int min(int a, int b) {
	if (a < b) return a;
	else return b;
    }

    private static int abs(int a) {
	if (a < 0) return -1*a;
	else return a;
    }

    public void simplify() {
	int nn = abs(n), dd = abs(d);
	int limite = min(nn, dd);

	boolean divisible[] = new boolean[limite + 1];
	eratosthene(divisible);

	boolean go_on = true;
	while (go_on) {
	    go_on = false;
	    for (int i = 2; i <= limite; i++)
		if (!divisible[i])
		    if (nn%i == 0 && dd%i == 0) {
			nn /= i; dd /= i;
			limite = min(nn, dd);
			go_on = true;
			break;
		    }
	}
	
	if ( (n >= 0 && d >= 0) || (n <= 0 && d <= 0) ) { n = nn; d = dd; }
	else { n = -1*nn; d = dd; }
    }


    public boolean isZero() {
	return n == 0;
    }

    /*
    public String toString() {
	String result = new String();
	result += n;
	if (n != 0 && d != 1) result += "/" + d; 
	return result;
    }
    */
}


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

(1) BareJBCToJBCProof (EQUIVALENT)
initialized classpath
----------------------------------------

(2)
Obligation:
need to prove termination of the following program:
public class EquationSystem {
    private Rational A[][];
    private Rational b[];
    private int n;

    public EquationSystem(Rational A[][], Rational b[]) {
	this.n = A.length;
	this.A = new Rational[n][n];
	this.b = new Rational[n];	
	for (int l = 0; l < n; l++) {
	    for (int c = 0; c < n; c++)
		this.A[l][c] = A[l][c]; 
	    this.b[l] = b[l];
	}
    }

    /*
    public void resolve() {
	if (diagonalize()) {
	    System.out.print("One solution = ");
	    System.out.print("(");
	    for (int l = 0; l < n; l++) {
		System.out.print(b[l]);
		if (l < n-1) System.out.print("; ");
	    }
	    System.out.println(").");
	}
	else System.out.println("Zero or an infinite number of solutions.");
    }
    */

    private int searchRow(int col) {
	for (int l = col; l < n; l++)
	    if (!A[l][col].isZero()) return l;
	return n;
    }

    private void permute(int l1, int l2) {
	Rational temp;
	for (int col = l1; col < n; col++) {
	    temp = A[l1][col];
	    A[l1][col] = A[l2][col]; 
	    A[l2][col] = temp;
	}
	temp = b[l1];
	b[l1] = b[l2];
	b[l2] = temp;
    }

    private void divide(int l, Rational pivot) {
	for (int col = l; col < n; col++) A[l][col].divideBy(pivot);
	b[l].divideBy(pivot);
    }

    private void substract(int i, int j) {
	Rational A_ji = new Rational(A[j][i]);
	for (int col = i; col < n; col++)
	    A[j][col].minus(A_ji.times(A[i][col]));
	b[j].minus(A_ji.times(b[i]));
    }

    public boolean diagonalize() {
	int current;
	Rational p;
	
	for (int l = 0; l < n; l++) {
	    current = searchRow(l);
	    if (current == n) return false;
	    p = new Rational(A[current][l]);
	    permute(l, current);
	    divide(l, p);
	    for (int ll = 0; ll < n; ll++)
		if (ll != l) substract(l, ll);
	}
	
	return true;
    }

    /*
    public String toString() {
	String res = "";
	for (int l = 0; l < n; l++) {
	    for (int col = 0; col < n-1; col++)
		res += A[l][col] + "*X" + col + " + ";
	    res += A[l][n-1] + "*X" + (n-1) + " = " + b[l] + "\n";
	}
	return res;
    }
    */

    public static void main (String args[]) {
	if (args.length >= 4) {
	    Rational A[][] = new Rational[1][1];
	    Rational b[]   = new Rational[1];
	    
	    A[0][0] = new Rational(args[0].length(), args[1].length());
	    b[0] = new Rational(args[2].length(), args[3].length());
	    
	    EquationSystem S = new EquationSystem(A, b);
	    // System.out.println(S);
	    // S.resolve();
	    S.diagonalize();
	}
    }
}


public class Rational {
    private int n, d;

    public Rational() {
	n = 0; d = 1;
    }

    public Rational(int num, int den) { 
	n = num; d = den;
    }

    public Rational(Rational r) {
	n = r.n; d = r.d;
    }

    public void minus(Rational r) {
	n = n*r.d - r.n*d;
	d *= r.d;
	simplify();
    }

    public Rational times(Rational r) {
	Rational result = new Rational(n*r.n, d*r.d);
	result.simplify();
	return result;
    }

    public void divideBy(Rational r) {
	n *= r.d; 
	d *= r.n;
	simplify();
    }

    private static void eratosthene(boolean T[]) {  
	for (int i = 0; i < T.length; i++) T[i] = false;
	if (T.length  <= 4) return;
	int number = 1;
	while (number*number < T.length) {
	    while ( T[++number] && number < T.length ) {};
	    for (int i = 2*number; i < T.length; i += number)
		T[i] = true;
	}
    }

    private static int min(int a, int b) {
	if (a < b) return a;
	else return b;
    }

    private static int abs(int a) {
	if (a < 0) return -1*a;
	else return a;
    }

    public void simplify() {
	int nn = abs(n), dd = abs(d);
	int limite = min(nn, dd);

	boolean divisible[] = new boolean[limite + 1];
	eratosthene(divisible);

	boolean go_on = true;
	while (go_on) {
	    go_on = false;
	    for (int i = 2; i <= limite; i++)
		if (!divisible[i])
		    if (nn%i == 0 && dd%i == 0) {
			nn /= i; dd /= i;
			limite = min(nn, dd);
			go_on = true;
			break;
		    }
	}
	
	if ( (n >= 0 && d >= 0) || (n <= 0 && d <= 0) ) { n = nn; d = dd; }
	else { n = -1*nn; d = dd; }
    }


    public boolean isZero() {
	return n == 0;
    }

    /*
    public String toString() {
	String result = new String();
	result += n;
	if (n != 0 && d != 1) result += "/" + d; 
	return result;
    }
    */
}