Abstract
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.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
“Un résultat sur les systèmes d'addition de vecteurs”, manuscript, INRIA Sophia Antipolis, France, feb. 1989.
“Bounds of non-negative integral solutions of linear diophantine equations”, Proc. AMS v.55, n.2, march 1976.
“Gröbner basis: an algorithmic method in polynomial ideal theory” Camp. Publ. Nr. 83-29. 0, nov. 1983.
“Solving systems of linear diophantine equations”, UNIF'89, proc. of the third international Workshop on unification, Lambrecht, RFA 89.
“Solving Systems fo Linear Diophantine Equations: An Algebraic Approch”, UNIF'90, International Workshop on Unification, Leeds UK, july 1990
“Algorithmes de calcul de bases standard”, Preprint Université de Nice, France, 1985.
“Total dual integrality and integer polyedra” Linear algebra and its applications, 25, pp191–196, 1979.
“An algorithm to generate the basis of solutions to homogeneous linear diophantine equations”, Information Processing Letters, vol.3, No.7, 1978.
“Exponent of periodicity of minimal solutions of word equations”, manuscript, University of Wroclaw, Poland, june 1990.
“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.
“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.
“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.
“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.
“Solutions of a linear diophantine system”, UNIF'89, proc. of the third international Workshop on unification, Lambrecht, RFA 89.
“Combinatorics and commutative algebra”, Progress in Mathematics, Birkäuser ed., 1983.
“Bounds in piecewise linear topology”, Trans.AMS, v.201, 1975.
“A bound on solutions of linear integer equalities and inequalities” Proc. AMS 72, pp155–158, 1978.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pottier, L. (1991). Minimal solutions of linear diophantine systems : bounds and algorithms. In: Book, R.V. (eds) Rewriting Techniques and Applications. RTA 1991. Lecture Notes in Computer Science, vol 488. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-53904-2_94
Download citation
DOI: https://doi.org/10.1007/3-540-53904-2_94
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-53904-9
Online ISBN: 978-3-540-46383-2
eBook Packages: Springer Book Archive