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

Details:

   
TitleA new Lower Bound Construction for Commutative Thue Systems with Applications
Author(s) Chee K. Yap
TypeArticle in Journal
AbstractWe improve the double-exponential
lower bound construction of Mayr and Meyer (1982)
for commutative semi-Thue systems.

For $n\\\\ge 1$ and $d\\\\ge 2$, I describe a
system with about 2n variables and O(n) rules, each
of size $d+O(1)$.

This construction implies the best current lower bound
on $D(n,d)$, $I(n,d)$ and $S(n,d)$
which are (respectively) the maximum degree of Groebner bases
generated by $n$-variate polynomials of degree $d$,
the associated ideal membership bound and
syzygy bound.
KeywordsLower bounds in Grobner bases, commutative semi-Thue systems, ideal membershipbound, syzygy bound, double exponential bound
LanguageEnglish
JournalJ. Symbolic Computation
Volume12
Pages1--28
Year1991
Edition0
Translation No
Refereed No
Webmaster