Algorithms for Finding Solutions to Positive Integers in a Linear System of Homogeneous Equations.

The authors are interested in finding positive-integer solutions to the system X**TC equals 0, where C is a matrix with integer coefficients. This problem arises when seeking invariants in a Petri net concerning which a few notions are briefly recalled. A theorem and its corollaries provide a description of the structure of all the solutions to the system. These results further make it possible to present a new proof of the resolution algorithm submitted by Farkas and to integrate into it an elegant optimization. The algorithm is exponential in space and time. Lastly, the authors describe a novel variant of the algorithm.