Minimal solutions of linear Diophantine systems: bounds and algorithms. (English) Zbl 1503.11152
Book, Ronald V. (ed.), Rewriting techniques and applications. 4th international conference, RTA-91, Como, Italy, April 10–12, 1991. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 488, 162-173 (1991).
Summary: We give new bounds and algorithms for minimal solutions of linear Diophantine systems. These bounds are simply exponential, while previous known bounds were, at least until recently, doubly exponential.
For the entire collection see [Zbl 0875.00122].
For the entire collection see [Zbl 0875.00122].
MSC:
| 11Y50 | Computer solution of Diophantine equations |
| 11Y16 | Number-theoretic algorithms; complexity |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | “Un résultat sur les systèmes d’addition de vecteurs”, manuscript, INRIA Sophia Antipolis, France, feb. 1989. |
| [2] | “Bounds of non-negative integral solutions of linear diophantine equations”, Proc. AMS v.55, n.2, march 1976. · Zbl 0291.10014 |
| [3] | “Gröbner basis: an algorithmic method in polynomial ideal theory” Camp. Publ. Nr. 83-29. 0, nov. 1983. |
| [4] | “Solving systems of linear diophantine equations“, UNIF”89, proc. of the third international Workshop on unification, Lambrecht, RFA 89. |
| [5] | “Solving Systems fo Linear Diophantine Equations: An Algebraic Approch“, UNIF”90, International Workshop on Unification, Leeds UK, july 1990 |
| [6] | “Algorithmes de calcul de bases standard”, Preprint Université de Nice, France, 1985. |
| [7] | “Total dual integrality and integer polyedra” Linear algebra and its applications, 25, pp191-196, 1979. · Zbl 0413.90054 |
| [8] | “An algorithm to generate the basis of solutions to homogeneous linear diophantine equations”, Information Processing Letters, vol.3, No.7, 1978. · Zbl 0377.10011 |
| [9] | “Exponent of periodicity of minimal solutions of word equations”, manuscript, University of Wroclaw, Poland, june 1990. |
| [10] | “Une borne pour les générateurs des solutions entières positives d’une équation diophantienne linéaire.“ Comptes Rendus de l”Académie des Sciences de Paris, t.305, Séire I, pp39-40, 1987. · Zbl 0615.10022 |
| [11] | “Un problème d’accessibilité dans les réseaux de Petri” Phd thesis, theorem I.5., p 18, University of Paris-Sud, Orsay, France, 1987. |
| [12] | “Le problème de l’identifiabilité structurelle globale: approche théorique, méthodes effectives et bornes de complexité”, Phd Thesis, Ecole Polytechnique, France, june 1990. |
| [13] | “Bornes et algorithmes de calcul des générateurs des solutions de systèmes diophantiens linéaires“, internal report, INRIA, feb. 90, Comptes Rendus de l”Académie des Sciences de Paris, t.311, Série I, p813-816,1990. · Zbl 0714.11018 |
| [14] | “Solutions of a linear diophantine system“, UNIF”89, proc. of the third international Workshop on unification, Lambrecht, RFA 89. |
| [15] | “Combinatorics and commutative algebra”, Progress in Mathematics, Birkäuser ed., 1983. · Zbl 0537.13009 |
| [16] | “Bounds in piecewise linear topology”, Trans.AMS, v.201, 1975. · Zbl 0301.57009 |
| [17] | “A bound on solutions of linear integer equalities and inequalities” Proc. AMS 72, pp155-158, 1978. · Zbl 0397.90071 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
