A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
From MaRDI portal
Publication:3753479
DOI10.1016/S0019-9958(86)80035-3zbMath0612.68033MaRDI QIDQ3753479
Publication date: 1986
Published in: Information and Control (Search for Journal in Brave)
Gröbner basisdegreecardinalityChurch-Rosser systemcommutative Thue systemdouble-exponential lower boundnormal form algorithmspolynomial ideal basisproduction length
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Software, source code, etc. for problems pertaining to commutative algebra (13-04) Thue and Post systems, etc. (03D03)
Related Items
On polynomial ideals, their complexity, and applications, Estimation under group actions: recovering orbits from invariants, Polly Two: a new algebraic polynomial-based public-key scheme, A new method for solving algebraic systems of positive dimension, An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, A deterministic algorithm to decide if a finitely presented abelian monoid is cancellative, Complexity of Gröbner basis detection and border basis detection, An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, and applications to commutative semigroups, Counting and Gröbner bases, Triangular sets for solving polynomial systems: a comparative implementation of four methods, Degree bounds for Gröbner bases in algebras of solvable type, On the complexity of the \(F_5\) Gröbner basis algorithm, A new lower bound construction for commutative Thue systems with applications
