REGULARITY OF MATRICES IN MIN-ALGEBRA AND ITS TIME-ALGEBRA COMPLEXITY

Let g = (G, +, less-than-or-equal-to) be a linearly ordered, commutative group and + be defined by a + b = min(a, b) for all a, b is-an-element-of G. Extend +, x to matrices and vectors as in conventional linear algebra. An n x n matrix A with columns A1, ..., A(n) is called regular if [GRAPHICS] does not hold for any lambda1, ..., lambda(n) is-an-element-of G, phi not-equal U, V subset-or-equal-to {1, 2, ..., n}, U and V = phi. We show that the problem of checking regularity is polynomially equivalent to the even cycle problem. We also present two other types of regularity which can be checked in O(n3) operations.