A new lower bound construction for commutative Thue systems with applications

DOI10.1016/S0747-7171(08)80138-1zbMath0731.68060OpenAlexW2031477970MaRDI QIDQ808265

Chee-Keng 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 systemmaximum degree Gröbner basismaximum 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)

Related Items (13)

A solution to Kronecker's problem ⋮ On polynomial ideals, their complexity, and applications ⋮ Complexity of Membership Problems of Different Types of Polynomial Ideals ⋮ Binomial ideals ⋮ New order bounds in differential elimination algorithms ⋮ Ideals generated by quadrics exhibiting double exponential degrees ⋮ Bounding the degrees of a minimal \(\mu\)-basis for a rational surface parametrization ⋮ Dimension and depth dependent upper bounds in polynomial ideal theory ⋮ 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 ⋮ On the parallel complexity of the polynomial ideal membership problem ⋮ A software tool for the investigation of plane loci ⋮ A sharp bound for the Castelnuovo-Mumford regularity of subspace arrangements.

Cites Work

• Fields of large transcendence degree generated by values of elliptic functions
• On the complexity of computing syzygies
• A note on upper bounds for ideal-theoretic problems
• The complexity of the word problems for commutative semigroups and polynomial ideals
• A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
• Constructions in Algebra
• Recursive Unsolvability of a problem of Thue
• Unnamed Item
• Unnamed Item

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