Details:
Title | A new Lower Bound Construction for Commutative Thue Systems with Applications | Author(s) | Chee K. Yap | Type | Article in Journal | Abstract | We 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.
| Keywords | Lower bounds in Grobner bases, commutative semi-Thue systems, ideal membershipbound, syzygy bound, double exponential bound |
Language | English | Journal | J. Symbolic Computation | Volume | 12 | Pages | 1--28 | Year | 1991 | Edition | 0 | Translation |
No | Refereed |
No |
|