A new lower bound construction for commutative Thue systems with applications
type: Item
instance of: scholarly article
title: A new lower bound construction for commutative Thue systems with applications
zbMATH Open document ID: 0731.68060
DOI: 10.1016/S0747-7171(08)80138-1
published in: Journal of Symbolic Computation
publication date: 1991-01-01T00:00:00Z
review text: The author describes a commutative Thue system with about 2n variables and O(n) rules, each of size \(d+0(1)\), that ``counts'' to \(d^{2^ n}\) in a certain technical sense. Using this construction he is able to sharpen the known double-exponential lower bounds for (i) the maximum degree D(n,d) of Gröbner basis, (ii) the maximum degree I(n,d) in ideal membership, and (iii) the maximum degree S(n,d) of the syzygy basis problem: \(D(n,d)\geq S(n,d)\geq d^{2^ m},\) \(I(n,d)\geq d^{2^ m},\) where \(m\sim n/2\), and n, d sufficiently large.
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 4209609
zbMATH Keywords: maximum degree Gröbner basis
zbMATH Keywords: maximum degree in ideal membership
zbMATH Keywords: maximum degree of the syzygy basis problem
zbMATH Keywords: commutative Thue system
zbMATH Keywords: lower bounds
author: Chee K. Yap
MaRDI profile type: Publication
cites work: On the complexity of computing syzygies
cites work: Q3710617
cites work: A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
cites work: A note on upper bounds for ideal-theoretic problems
cites work: Fields of large transcendence degree generated by values of elliptic functions
cites work: The complexity of the word problems for commutative semigroups and polynomial ideals
cites work: Q3678669
cites work: Recursive Unsolvability of a problem of Thue
cites work: Constructions in Algebra
full work available at URL: s0747-7171(08)80138-1
OpenAlex ID: W2031477970
Recommended article: On finite commutative Thue systems
Recommended article: On reduced thue systems
Recommended article: A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
Recommended article: On a method for proving exact bounds on derivational complexity in Thue systems
Recommended article: Q4014422
Recommended article: Q3153443
Recommended article: On the regular equivalence problem for regular Thue systems
Recommended article: The Knuth-Bendix Completion Procedure and Thue Systems
Recommended article: Q3346296
Recommended article: Q3319767
description: scientific article; zbMATH DE number 4209609