In: Artificial Intelligence, no. 1, pages 29-37. 2004. In Russian.
Abstract: Estimation of time and space complexity of Toudic method aimed to solution of homogeneous linear Diophantine systems of equations in nonnegative integer numbers is implemented. Conditions of polynomial complexity of method are obtained. It was shown that in the worst case calculation complexity of the method is double exponential with respect to dimension of a system. It was found that for sparse matrixes there is a flood effect resulting in estimations of complexity in the worst case.
Keywords: Petri net; invariant; Toudic method; double exponent; flood effect.