Title | **Some complexity results for prefix Gröbner bases in free monoid rings** |

Author(s) | Andrea Sattler-Klein |

Type | Article in Journal |

Abstract | We 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]. |

Keywords | Algorithms, Computational complexity, Rewriting, Gröbner bases, Free monoid rings |

ISSN | 0304-3975 |

URL |
http://www.sciencedirect.com/science/article/pii/S0304397509007609 |

Language | English |

Journal | Theoretical Computer Science |

Volume | 411 |

Number | 4–5 |

Pages | 823 - 833 |

Year | 2010 |

Note | Fundamentals of Computation Theory |

Edition | 0 |

Translation |
No |

Refereed |
No |