Constructions of standard bases of right K A- modules

DOI10.1016/0304-3975(93)90318-NMaRDI QIDQ688707zbMATH OpenOpenAlexFDO

Publication date 13 September 1994

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(93)90318-n

algorithm free associative \(K\)-algebra free monoid Gröbner bases membership prefix code well ordering

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Ideals in associative algebras (16D25) Associative rings determined by universal properties (free algebras, coproducts, adjunction of inverses, etc.) (16S10) Combinatorics on words (68R15) Symbolic computation and algebraic computation (68W30)

Review text

Let \(K\langle A\rangle\) be the free associative \(K\)-algebra (\(K\) is a field) over an alphabet \(A\). The author constructs a variant of Gröbner bases for right \(K\langle A\rangle\)-submodules of the right \(K\langle A\rangle\)-module \(K\langle A\rangle^ q\). We describe his construction for \(q = 1\); the generalization for \(q > 1\) is more or less straightforward. Let \(\leq\) be a well ordering on the free monoid \(A^*\) such that \(u\leq v\) implies \(uw\leq vw\) and \(w=uv\) implies \(u\leq w\) for all \(u,v,w\in A^*\). For a polynomial \(P\in K\langle A\rangle\), the leading word \(r(P)\) of \(P\) is the maximal (under \(\leq\)) word from \(A^*\) appearing in the irreducible representation of \(P\) as a \(K\)-linear combination of elements of \(A^*\). Now let \(I\) be a right \(K\langle A\rangle\)-submodule (i.e. a right ideal) in \(K\langle A\rangle\). A family \(\{w_ i\}_{i\geq 1}\) is said to be \(K\)-dependent mod \(I\) if there are \(\alpha_ i\in K\) such that \(\sum_{n\geq 1}\alpha_ i w_ i\in I\). Define \(u_ 1 =\inf\{w\in A^*:\{v\leq w\}\) is \(K\)-dependent mod \(I\)\} and, for \(n\geq 2\), \(u_ n =\inf\{w\in A^*\setminus\{u_ 1,\dots,u_{n-1}\}A^*:\{v\leq w\}\cap A^*\setminus\{u_ 1,\dots,u_{n-1}\}A^*\) is \(K\)-dependent mod \(I\}\). The family \(\{u_ n\}_{n\geq 1}\) turns out to be a prefix code such that \(u_ i < u_ j\) whenever \(i < j\); it is finite iff \(I\) is finitely generated. For each \(n\), there exists a polynomial \(P_ n\in I\) such that \(r(P_ n) = u_ n\) and the leading coefficient of \(P_ n\) is equal to 1. The family \(\{P_ n\}_{n\geq 1}\) generates \(I\) and is called the standard basis of \(I\); it is proved that it is in a sense unique. The main result of the paper provides an algorithm which, given a finite family \(Q_ 1,\dots,Q_ k\) of polynomials, constructs a standard basis of the right ideal of \(K\langle A\rangle\) generated by \(Q_ 1,\dots,Q_ k\). As corollaries, the author proves that it is possible to recognize whether two finite sets of polynomials generate the same right ideal and to test the membership of a given polynomial to the right ideal generated by a given finite family of polynomials.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Constructions of standard bases of right \(K\langle A\rangle\)- modules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q688707)