It has been understood recently that numerous problems in graph theory, matrix manipulation, finite automata, etc., are just different incarnations of the same general problem. These problems include paths in graphs, connectivity, matrix multiplication, systems of linear equations, regular expressions, and many others.
In the last ten years, there have been several attempts to propose a general framework that describes all these problems in a uniform way. Various approaches were taken: regular expressions, matrix multiplications, and the closure operation in semirings.
This paper presents yet another attempt to give a unified approach to this class of problems. It is a refinement of the approach proposed in [1]. The main contribution of the paper is the concept of the eliminant (equivalent to the determinant in linear algebra). The authors use it as a basis for a new formulation of the problems in question. Their formulation is a bit simpler than the one found in Lehmann’s paper [1] and much simpler than that in Tarjan’s report on the same subject [2]. It is unfortunate, however, that the paper is so short: much would be gained by giving a broader context (e.g., examples of problems that cannot be reduced to semiring closure, etc.).
By the very nature of the subject, this paper does not contain new algorithms, but a new methodology. As a result, it should be of interest not only to those who are interested in the specific problems involved, but to all researchers interested in computational complexity.