×
Chapman, S. T.; García-Sánchez, P. A.; Llena, D.; Rosales, J. C.

Presentations of finitely generated cancellative commutative monoids and nonnegative solutions of systems of linear equations. (English) Zbl 1106.20046

Discrete Appl. Math. 154, No. 14, 1947-1959 (2006).
The authors investigate three types of algorithms for computing presentations of finitely generated commutative cancellative monoids. The problem is reduced to a system of linear equations and linear congruences. The authors also show how such presentations can be efficiently computed from an integer basis.
The implementation of the first group of algorithms depends on the computation of Gröbner bases; the second group of algorithms is based on the computation of a minimal presentation of a numerical semigroup and the third one is devoted to the computation of irreducibles.
Reviewer: Robert F. Tichy (Graz)

Cited in 8 Documents

MSC:

20M14 Commutative semigroups
20M05 Free semigroups, generators and relations, word problems
68W30 Symbolic computation and algebraic computation
11Y50 Computer solution of Diophantine equations

Keywords:

finitely generated commutative cancellative monoids; presentations; systems of linear equations; computation; algorithms; numerical semigroups

Software:

GAP; numericalsgps
Cite Review PDF
Full Text: DOI Link

References:

[1] Briales, E.; Campillo, A.; Marijuán, C.; Pisón, P., Minimal systems of generators for ideals of semigroups, J. Pure Appl. Algebra, 124, 7-30 (1998) · Zbl 0913.20036
[2] Chapman, S. T.; García-García, J. I.; García-Sánchez, P. A.; Rosales, J. C., Computing the elasticity of a Krull monoid, Linear Algebra Appl., 336, 191-200 (2001) · Zbl 0995.20040
[3] Clausen, M.; Fortenbacher, A., Efficient solution of linear Diophantine equations, J. Symbolic Comput., 8, 1-2, 201-216 (1989) · Zbl 0674.10011
[4] Contejean, E.; Devie, H., An efficient incremental algorithm for solving systems of linear diophantine equations, Inform. and Comput., 113, 143-172 (1994) · Zbl 0809.11015
[5] M. Delgado, P.A. García-Sánchez, J. Morais, numericalsgps: a \(\textsf{GAP} \langle;\) http://www.gap.system.org \(\rangle;\langle;\) http://www.gap-system.org/Packages/numericalsgps.html \(\rangle;\); M. Delgado, P.A. García-Sánchez, J. Morais, numericalsgps: a \(\textsf{GAP} \langle;\) http://www.gap.system.org \(\rangle;\langle;\) http://www.gap-system.org/Packages/numericalsgps.html \(\rangle;\)
[6] Di Biase, F.; Urbanke, R., An algorithm to calculate the kernel of certain polynomial ring homomorphisms, Experimental Math., 4, 3, 227-234 (1995) · Zbl 0860.68062
[7] E. Domenjoud, A.P. Tomás, From Elliott-MacMahon to an algorithm for general linear constraints on naturals, Principles and Practice of Constraint Programming—CP ’95, Cassis, 1995, Lecture Notes in Computer Science, vol. 976, Springer, Berlin, 1995, pp. 18-35.; E. Domenjoud, A.P. Tomás, From Elliott-MacMahon to an algorithm for general linear constraints on naturals, Principles and Practice of Constraint Programming—CP ’95, Cassis, 1995, Lecture Notes in Computer Science, vol. 976, Springer, Berlin, 1995, pp. 18-35.
[8] Herzog, J., Generators and relations of abelian semigroups and semigroup rings, Manuscripta Math., 3, 175-193 (1970) · Zbl 0211.33801
[9] P. Pisón, A. Vignerón Tenorio, Ideales de semigroups con torsión: cálculos mediante Maple V, EACA’96, Universidad de Sevilla, 1996.; P. Pisón, A. Vignerón Tenorio, Ideales de semigroups con torsión: cálculos mediante Maple V, EACA’96, Universidad de Sevilla, 1996.
[10] Pisón, P.; Vignerón Tenorio, A., \(N\)-solutions to linear systems over \(Z\), Linear Algebra Appl., 384, 135-154 (2004) · Zbl 1126.13020
[11] Pottier, L., Bornes et algorithme de calcul des générateurs des solutions de systèmes diophantiens linéaires, C. R. Acad. Sci. Paris, 311, Série I, 813-816 (1990) · Zbl 0714.11018
[12] L. Pottier, Minimal solutions of linear diophantine systems: bounds and algorithms, Rewriting Techniques and Applications, Como, 1991, Lecture Notes in Computer Science, vol. 488, Springer, Berlin, 1991, pp. 162-173.; L. Pottier, Minimal solutions of linear diophantine systems: bounds and algorithms, Rewriting Techniques and Applications, Como, 1991, Lecture Notes in Computer Science, vol. 488, Springer, Berlin, 1991, pp. 162-173. · Zbl 1503.11152
[13] Rédei, L., The Theory of Finitely Generated Commutative Semigroups (1965), Pergamon Press: Pergamon Press Oxford · Zbl 0133.27904
[14] Rosales, J. C., On finitely generated submonoids of \(N^k\), Semigroup Forum, 50, 251-262 (1995) · Zbl 0831.20080
[15] Rosales, J. C., An algorithmic method to compute a minimal relation for any numerical semigroup, Internat. J. Algebra Comput., 6, 4, 441-455 (1996) · Zbl 0863.20026
[16] Rosales, J. C.; García-Sánchez, P. A., Nonnegative elements of subgroups of \(N^n\), Linear Algebra Appl., 270, 351-357 (1998) · Zbl 0890.15016
[17] Rosales, J. C.; García-Sánchez, P. A., Finitely Generated Commutative Monoids (1999), Nova Science Publishers: Nova Science Publishers New York · Zbl 0966.20028
[18] Rosales, J. C.; García-Sánchez, P. A.; García-García, J. I., Presentations of finitely generated submonoids of finitely generated commutative monoids, Internat. J. Algebra Comput., 12, 5, 659-670 (2002) · Zbl 1010.20049
[19] Rosales, J. C.; García-Sánchez, P. A.; Urbano-Blanco, J. M., On presentations of commutative monoids, Internat. J. Algebra Comput., 9, 5, 539-553 (1999) · Zbl 1028.20037
[20] Rosales, J. C.; Urbano-Blanco, J. M., A deterministic algorithm to decide if a finitely presented abelian monoid is cancellative, Comm. Algebra, 24, 13, 4217-4224 (1996) · Zbl 0940.20058
[21] Sturmfels, B., Gröbner bases of toric varieties, Tôhoku Math. J., 43, 249-261 (1991) · Zbl 0714.14034
[22] Sturmfels, B., Gröbner bases and convex polytopes, University Lecture Series, vol. 8 (1996), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 0856.13020
[23] The \(\textsf{GAP} \langle;\) http://www.gap-system.org \(\rangle;\); The \(\textsf{GAP} \langle;\) http://www.gap-system.org \(\rangle;\)
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.