Modification of algorithm for constructing minimal supported set of solutions of SLE over the set of natural numbers
Keywords:
Діофантові рівняння, алгоритм, розв’язання, складністьAbstract
The work presents optimization transformations of the algorithm for constructing the minimum supported set of solutions of the system of linear equations in the set of natural numbers, which improve the time characteristics of this algorithm.
References
Gordan P. Ueber die Auflösung linearen Gleidungen mit reallen Coefficienten. Mathematische Annalen, 1873, № 6, P. 23–28.
Hilbert D. Ueber die Theorie der algebraischen Formen. Mathematische Annalen, 1890, № 36, – P. 473–534.
Clausen M., Fortenbacher A. Efficient solution of linear diophantine equations. Journ. Symbolic Computation, 1989, v.8. № 1,2. – P. 201–216.
Contenjean E., Devie H. An efficient algorithm for solving systems of Diophantine equations, Inform. Comput, 1994, № 113, v. 1. – P. 143–172.
Domenjoud E. Outils pour la deduction automatique dans les theories associatives-commutatives. Thesis de Doctorat d'Universite: Universite de Nancy I, 1991.
Pottier L. Minimal solution of linear diophantine systems: bounds and algorithms. In Proceed. of the 4-th Intern. Conf. on Rewriting Techniques and Applications, Como, Italy, 1991, – P.162–173.
Kryvyi S. Calculation of the minimal set of Petri net’s invariants. J. Artificial intelligence. 2001, № 3. pp. 199-206.
Kryvyi S. Linear Diophantine constraints and their applications. Kyiv: Interservis. 2021. – 260 p.
Hermann M., Juban L., Kolaitis P. G. On the Complexity of Counting the Hilbert Basis of a Linear Diophantine System. Springer Verlag, LNCS, 1999, № 1705. – P. 13–32.
