From monomials to words to graphs. (Q598451)

Starting from a finite alphabet \(X\), let \([X]\) be the free commutative monoid on \(X\), and let \(X^*\) be the free monoid on \(X\). The members of \(X\) are called `letters', the members of \([X]\) `monomials', and the ones of \(X^*\) `words'. For each ordering \(\prec\) of the letters, let \(\sigma\colon[X]\to X^*\) be the function that maps a monomial to the word that is the ordered product of the letter powers in the monomial. In this paper, the authors consider problems that were motivated by the study of noncommutative presentations of affine algebras and their Gröbner bases. Given an ideal \(I\) in \([X]\) and an ordering \(\prec\) of \(X\), the authors describe in particular a polynomial-time algorithm to decide whether the ideal \(\langle\sigma_\prec(I)\rangle\) generated by \(\sigma_\prec(I)\) in the free monoid is finitely generated. Also, given an ideal \(I\) in \([X]\), they show that whether there exists an ordering \(\prec\) such that \(\langle\sigma_\prec(I)\rangle\) is finitely generated is an NP-complete problem closely related to the recognition problem for comparability graphs.