Presentations of finitely generated cancellative commutative monoids and nonnegative solutions of systems of linear equations

Varying methods exist for computing a presentation of a finitely generated commutative cancellative monoid. We use an algorithm of Contejean and Devie [An efficient incremental algorithm for solving systems of linear diophantine equations, Inform. and Comput. 113 (1994) 143–172] to show how these pr...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2006-09, Vol.154 (14), p.1947-1959
Main Authors: Chapman, S.T., García-Sánchez, P.A., Llena, D., Rosales, J.C.
Format: Article
Language:English
Subjects:
Exact sciences and technology
Finitely generated commutative cancellative monoid
Group theory
Group theory and generalizations
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Numerical linear algebra
Sciences and techniques of general use
System of linear equations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Varying methods exist for computing a presentation of a finitely generated commutative cancellative monoid. We use an algorithm of Contejean and Devie [An efficient incremental algorithm for solving systems of linear diophantine equations, Inform. and Comput. 113 (1994) 143–172] to show how these presentations can be obtained from the nonnegative integer solutions to a linear system of equations. We later introduce an alternate algorithm to show how such a presentation can be efficiently computed from an integer basis.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2006.03.013