Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleAn algorithm for constructing Gröbner and free Schreier bases in free group algebras
Author(s) Amnon Rosenmann
TypeArticle in Journal
AbstractWe present an algorithm for computing Gröbner and free canonical Schreier bases for finitely generated one-sided ideals in free group algebras. That is, given a set of n elements of a free group algebra, we construct a canonical Schreier basis of free generators as well as a Gröbner basis for the right ideal generated by the original set. In contrast to Buchberger's algorithm in polynomial rings, at any stage the current number of polynomials does not exceed 2n and their maximal degree is bounded by d 2, where d is the maximal degree of the original polynomials.
A corollary is that the generalised membership problem for free group algebras is solvable.
As a special case we obtain an algorithm similar to the Nielsen-Hall algorithm for constructing free bases for subgroups of free groups.
A generalisation of the notion of a Gröbner basis is given by the definition of algebras satisfying constructive division algorithms.
ISSN0747-7171
URL dx.doi.org/10.1006/jsco.1993.1061
LanguageEnglish
JournalJournal of Symbolic Computation
Volume16
Number6
Pages523-549
PublisherAcademic Press, Inc.
AddressDuluth, MN, USA
Year1993
Translation No
Refereed Yes
Webmaster