A new lower bound construction for commutative Thue systems with applications

DOI10.1016/S0747-7171(08)80138-1MaRDI QIDQ808265zbMATH OpenOpenAlexFDO

Authors Chee K. Yap

Publication date 1991

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0747-7171(08)80138-1

zbMATH Keywords

lower boundscommutative Thue system[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=maximum+degree+Gr%EF%BF%BD%EF%BF%BDbner+basis&go=Go maximum degree Gr��bner basis]maximum degree in ideal membershipmaximum degree of the syzygy basis problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Parallel algorithms in computer science (68W10) Thue and Post systems, etc. (03D03)

Recommendations

• On finite commutative Thue systems
• On reduced thue systems
• A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
• On a method for proving exact bounds on derivational complexity in Thue systems
• Publication:4014422
• Publication:3153443
• On the regular equivalence problem for regular Thue systems
• The Knuth-Bendix Completion Procedure and Thue Systems
• Publication:3346296
• Publication:3319767

Cites work

• scientific article; zbMATH DE number 3900153 (Why is no real title available?)
• scientific article; zbMATH DE number 3937298 (Why is no real title available?)
• A note on upper bounds for ideal-theoretic problems
• A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
• Constructions in Algebra
• Fields of large transcendence degree generated by values of elliptic functions
• On the complexity of computing syzygies
• Recursive unsolvability of a problem of Thue
• The complexity of the word problems for commutative semigroups and polynomial ideals

Cited in

(14)

• Bounding the degrees of a minimal \(\mu\)-basis for a rational surface parametrization
• Binomial ideals
• On the parallel complexity of the polynomial ideal membership problem
• Ideals generated by quadrics exhibiting double exponential degrees
• Complexity of a standard basis of a \(D\)-module.
• Double-exponential lower bound for the degree of any system of generators of a polynomial prime ideal
• Complexity of membership problems of different types of polynomial ideals
• On polynomial ideals, their complexity, and applications
• A software tool for the investigation of plane loci
• New order bounds in differential elimination algorithms
• A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
• A solution to Kronecker's problem
• A sharp bound for the Castelnuovo-Mumford regularity of subspace arrangements.
• Dimension and depth dependent upper bounds in polynomial ideal theory

This page was built for publication: A new lower bound construction for commutative Thue systems with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808265)