2003/02/20 by Cristina G. Fernandes, Edward L. Green, Fernandes, Cristina G. +3
Computer Science · Mathematics · #05C17 #13P10 #16Z05 #68Q25 #68R15 #Advanced Algebra and Logic #Combinatorics (math.CO) #Commutative Algebra (math.AC) #Commutative Algebra and Its Applications #FOS: Mathematics #Group Theory (math.GR) #math.AC #math.CO #math.GR #msc:05C17 #msc:13P10 #msc:16Z05 #msc:68Q25 #msc:68R15 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0302252
27 pages, 2 postscript figures, uses gastex.sty
arxiv created 2003/02/20 · openalex publication_date 2003/02/20 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a finite alphabet X and an ordering on the letters, the map σsends each monomial on X to the word that is the ordered product of the letter powers in the monomial. Motivated by a question on Groebner bases, we characterize ideals I in the free commutative monoid (in terms of a generating set) such that the ideal generated by σ(I) in the free monoid is finitely generated. Whether there exists an ordering such that is finitely generated turns out to be NP-complete. The latter problem is closely related to the recognition problem for comparability graphs.