The complexity of the word problems for commutative semigroups and polynomial ideals

DOI10.1016/0001-8708(82)90048-2zbMath0506.03007OpenAlexW2013504313WikidataQ56391720 ScholiaQ56391720MaRDI QIDQ1836661

Publication date: 1982

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0001-8708(82)90048-2

zbMATH Keywords

upper bound exponential complexity uniform word problem polynomial ideal word problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Commutative semigroups (20M14) Complexity of computation (including implicit computational complexity) (03D15) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40) Word problems (aspects of algebraic structures) (08A50)

Related Items (only showing first 100 items - show all)

Algorithmic aspects of Suslin's proof of Serre's conjecture ⋮ Subadditivity of Syzygies of Ideals and Related Problems ⋮ Regularity Bounds by Projection ⋮ Regularity of prime ideals ⋮ On polynomial ideals, their complexity, and applications ⋮ The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups ⋮ Unnamed Item ⋮ Weak Bézout inequality for D-modules ⋮ IMPLICATIONAL RELEVANCE LOGIC IS 2-EXPTIME-COMPLETE ⋮ Complexity of Membership Problems of Different Types of Polynomial Ideals ⋮ Effective Bezout identities in \({\mathbb{Q}}[z_ 1,\dots ,z_ n\)] ⋮ On the Effective Membership Problem for Polynomial Ideals ⋮ An Effective Uniform Artin–Rees Lemma ⋮ The regularity conjecture for prime ideals in polynomial rings ⋮ Computational aspects of the coordinate ring of an algebraic variety ⋮ Annual Meeting of the Association for Symbolic Logic, Los Angeles, 1989 ⋮ A factorization algorithm for \(G\)-algebras and its applications ⋮ Membership in polynomial ideals over Q is exponential space complete ⋮ Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism ⋮ Generalized typical dimension of a graded module ⋮ Kac-Rice formulas and the number of solutions of parametrized systems of polynomial equations ⋮ Conormal spaces and Whitney stratifications ⋮ Syzygies over a polynomial ring ⋮ Residue currents with prescribed annihilator ideals ⋮ Modularity and Combination of Associative Commutative Congruence Closure Algorithms enriched with Semantic Properties ⋮ \texttt{tapir}: a tool for topologies, amplitudes, partial fraction decomposition and input for reductions ⋮ Counting roots for polynomials modulo prime powers ⋮ Alternatives for testing total dual integrality ⋮ Segre-driven radicality testing ⋮ Classifying the computational complexity of problems ⋮ Population protocols: beyond runtime analysis ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ Linear syzygies, hyperbolic Coxeter groups and regularity ⋮ Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices ⋮ The Monomial Ideal Membership Problem and Polynomial Identity Testing ⋮ Notes on regularity stabilization ⋮ Gröbner Bases in D-Modules: Application to Bernstein-Sato Polynomials ⋮ Comparison of theoretical complexities of two methods for computing annihilating ideals of polynomials ⋮ Bounds for the Castelnuovo-Mumford regularity of modules ⋮ ON COMPLEXITY OF THE SATISFIABILITY PROBLEM OF SYSTEMS OVER FINITE POSETS ⋮ DECIDABILITY OF THE RESTRICTED THEORIES OF A CLASS OF PARTIAL ORDERS ⋮ Synthesis and Analysis of Product-Form Petri Nets ⋮ Varieties of Commutative Semigroups ⋮ A Framework for Classical Petri Net Problems: Conservative Petri Nets as an Application ⋮ An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, and applications to commutative semigroups ⋮ Counting and Gröbner bases ⋮ Solution of a conjecture of C. Berenstein - A. Yger and invariants of contact at infinity ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ Computing bases of complete intersection rings in Noether position ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the complexity of reasoning in Kleene algebra ⋮ On computing absolutely irreducible components of algebraic varieties with parameters ⋮ Symbolic Computation and Complexity Theory Transcript of My Talk ⋮ A finitely axiomatizable undecidable equational theory with recursively solvable word problems ⋮ An Upper Bound for the Regularity of Ideals of Borel Type ⋮ Double-exponential lower bound for the degree of any system of generators of a polynomial prime ideal ⋮ Three themes of syzygies ⋮ Need Polynomial Systems Be Doubly-Exponential? ⋮ Unnamed Item ⋮ Ideal membership in polynomial rings over the integers ⋮ On Model Checking Boolean BI ⋮ The Complexity of Cylindrical Algebraic Decomposition with Respect to Polynomial Degree ⋮ Decision procedure of some relevant logics: a constructive perspective ⋮ Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable ⋮ Linearization of resolutions via products ⋮ Combining Equational Reasoning ⋮ Regularity of structure sheaves of varieties with isolated singularities ⋮ The degree of a tropical basis ⋮ Counterexamples to the Eisenbud–Goto regularity conjecture ⋮ On the complexity of the \(F_5\) Gröbner basis algorithm ⋮ Global effective versions of the Briançon-Skoda-Huneke theorem ⋮ On polynomial vector fields having a given affine variety as attractive and invariant set: application to robotics ⋮ Linearly presented modules and bounds on the Castelnuovo-Mumford regularity of ideals ⋮ Multilevel polynomial partitions and simplified range searching ⋮ Linear logic as a logic of computations ⋮ A solution to Kronecker's problem ⋮ On the embedded primes of the Mayr-Meyer ideals ⋮ Symmetry reductions and exact solutions of a class of nonlinear heat equations ⋮ Testing binomiality of chemical reaction networks using comprehensive Gröbner systems ⋮ Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ The complexity of elementary algebra and geometry ⋮ An exercise in structural congruence ⋮ Linear syzygies, flag complexes, and regularity ⋮ A characterization of semisimple plane polynomial automorphisms ⋮ Computer algebra: Past and future ⋮ The complexity of reachability in distributed communicating processes ⋮ Open problems on syzygies and Hilbert functions ⋮ Bounds for the Castelnuovo-Mumford regularity ⋮ Petri nets, Horn programs, linear logic and vector games ⋮ Codeterminantal graphs ⋮ The word and generator problems for lattices ⋮ A Pommaret bases approach to the degree of a polynomial ideal ⋮ Completeness results for conflict-free vector replacement systems ⋮ Bounds on the regularity and projective dimension of ideals associated to graphs ⋮ On the complexity of computing syzygies ⋮ Counting solutions to binomial complete intersections ⋮ Linear logic automata ⋮ Binomial ideals ⋮ Extended \(F_5\) criteria

Cites Work

This page was built for publication: The complexity of the word problems for commutative semigroups and polynomial ideals