Regular Gröbner bases (Q1599541): Difference between revisions

\textit{V. A. Ufnarovskij} [Mat. Sb. 180, No. 11, 1548-1560 (1989; Zbl 0685.16007)] defined automaton algebras. These are finitely generated algebras such that the normal words modulo the defining ideal constitute a normal set. Let \(X\) be a finite set of generators and \({\mathcal X}=(X\times\{1\})\cup(\{1\}\times X)\). Given a semigroup ordering on the free semigroup \(X^*\), a Gröbner basis \(G\) for an ideal \(I\) in the free associative algebra \(k\langle X\rangle\) is a subset \(G\subseteq I\) such that the set of leading words of \(G\) generates the set of leading words of \(I\) as monomial ideal. A Gröbner basis is said to be regular if it consists of pure binomials (i.e., differences of two words) and these binomials are obtained from a set of regular words \(S\) in \(\mathcal X\). An algebra is said to be bi-automaton if the defining ideal admits a regular Gröbner basis. Bi-automaton implies automaton and most of the examples handled by Ufnarovskij are bi-automaton. Subalgebras of \(k\langle X \rangle\) generated by words are isomorphic to bi-automaton algebras. Moreover, subalgebras having a finite SAGBI basis are isomorphic to automaton algebras. The reductions in an algebra with a Gröbner basis \(G\) can be implemented if \(G\) is finite. In the infinite case, if \(G\) is regular the automaton accepting the regular set \(S\) allows the implementation of reductions. A previous algorithm of the authors can be used to predict a possible infinite regular Gröbner basis for an ideal given by pure binomials.