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

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, Ideals generated by quadrics exhibiting double exponential degrees, Castelnuovo-Mumford regularity and computing the de Rham cohomology of smooth projective varieties, Primary components of codimension two lattice basis ideals, A note on the regularity of Hibi rings, Integration-by-parts reductions of Feynman integrals using singular and GPI-space, The minimal components of the Mayr-Meyer ideals., Complexity of some language fragments of fuzzy logics, Algorithms for computing greatest common divisors of parametric multivariate polynomials, Combinatorial dimension theory of algebraic varieties, Local zero estimates and effective division in rings of algebraic power series, Word problems over traces which are solvable in linear time, Generalised characteristic polynomials, On the maximal graded shifts of ideals and modules, Fast theorem-proving and Wu's method, On some configurations of oppositely charged trapped vortices in the plane, A polynomial-time algorithm to compute generalized Hermite normal forms of matrices over \(\mathbb{Z} [x\)], Reconstructing biochemical cluster networks, Complexity of computations in Commutative Division of the USSR Academy of Sciences, The degree-complexity of the defining ideal of a smooth integral curve, Some issues on the automatic computation of plane envelopes in interactive environments, Equations for the projective closure and effective Nullstellensatz, The membership problem for unmixed polynomial ideals is solvable in single exponential time, An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, The complexity of problems involving structurally bounded and conservative Petri nets, Dehn functions of finitely presented metabelian groups, Complexity of solution of linear systems in rings of differential operators, Decision problems for propositional linear logic, A bound for a typical differential dimension of systems of linear differential equations, Extended parallelism in the Gröbner basis algorithm, Computation of Hilbert functions, Bouziane's transformation of the Petri net reachability problem and incorrectness of the related algorithm, The ideal membership problem and polynomial identity testing, Many associated primes of powers of primes, Subadditivity of syzygies of Koszul algebras, Normal and sinkless Petri nets, Using machine learning to improve cylindrical algebraic decomposition, A bound for orders in differential Nullstellensatz, A generic effective Nullstellensatz, Properness defects of projection and minimal discriminant variety, An exact algebraic \(\epsilon \)-constraint method for bi-objective linear integer programming based on test sets, Dimension and depth dependent upper bounds in polynomial ideal theory, Efficiently and effectively recognizing toricity of steady state varieties, Towards massively parallel computations in algebraic geometry, Algebraic algorithms for sampling from conditional distributions, Notes on Gröbner bases, Triangular sets for solving polynomial systems: a comparative implementation of four methods, Solving degenerate sparse polynomial systems faster, Complexity of deciding Tarski algebra, Gröbner bases of toric varieties, Polynomial bounds in polynomial rings over fields, Non-commutative Gröbner bases in algebras of solvable type, Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields, Cylindrical algebraic decomposition with equational constraints, On the parallel complexity of the polynomial ideal membership problem, A multiparameter analysis of the boundedness problem for vector addition systems, Composable computation in discrete chemical reaction networks, Toward an efficient algorithm for deciding the vanishing of local cohomology modules in prime characteristic, Computation of Macaulay constants and degree bounds for Gröbner bases, Complexity bounds in elimination theory -- a survey., Projections of vector addition system reachability sets are semilinear, Univariate ideal membership parameterized by rank, degree, and number of generators, A combinatorial approach to involution and \(\delta \)-regularity. II: Structure analysis of polynomial modules with Pommaret bases, Trajectories of polynomial vector fields and ascending chains of polynomial ideals, Explicit polynomial bounds on prime ideals in polynomial rings over fields, Algorithms for residues and Łojasiewicz exponents, Bounds on the torsion subgroup schemes of Néron-Severi group schemes, Deciding the word problem for ground and strongly shallow identities w.r.t. extensional symbols, Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups., Computing a context-free grammar-generating series, Complexity of the word problem for commutative semigroups of fixed dimension, Efficient localization at a prime ideal without producing unnecessary primary components, Enumerating a subset of the integer points inside a Minkowski sum, A new lower bound construction for commutative Thue systems with applications, Polynomial ideals for sandpiles and their Gröbner bases, A sharp bound for the Castelnuovo-Mumford regularity of subspace arrangements.

Cites Work