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

Details:

   
TitleSome complexity results for prefix Gröbner bases in free monoid rings
Author(s) Andrea Sattler-Klein
TypeArticle in Journal
AbstractWe establish the following complexity results for prefix Gröbner bases in free monoid rings: 1. | R | ⋅ s i z e ( p ) reduction steps are sufficient to normalize a given polynomial p w.r.t. a given right-normalized system R of prefix rules compatible with some total admissible well-founded ordering >. 2. O ( | R | ⋅ s i z e ( R ) ) basic steps are sufficient to transform a given terminating system R of prefix rules into an equivalent right-normalized system. 3. O ( | R | 2 ⋅ s i z e ( R ) ) basic steps are sufficient to decide whether or not a given terminating system R of prefix rules is a prefix Gröbner basis. The latter result answers an open question posed by Zeckzer (2000) [9].
KeywordsAlgorithms, Computational complexity, Rewriting, Gröbner bases, Free monoid rings
ISSN0304-3975
URL http://www.sciencedirect.com/science/article/pii/S0304397509007609
LanguageEnglish
JournalTheoretical Computer Science
Volume411
Number45
Pages823 - 833
Year2010
NoteFundamentals of Computation Theory
Edition0
Translation No
Refereed No
Webmaster