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

DOI10.1016/0001-8708(82)90048-2zbMath0506.03007WikidataQ56391720 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

68Q25: Analysis of algorithms and problem complexity

20M14: Commutative semigroups

03D15: Complexity of computation (including implicit computational complexity)

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

03D40: Word problems, etc. in computability and recursion theory

08A50: Word problems (aspects of algebraic structures)

Related Items

Varieties of Commutative Semigroups, Ideal membership in polynomial rings over the integers, A finitely axiomatizable undecidable equational theory with recursively solvable word problems, The Monomial Ideal Membership Problem and Polynomial Identity Testing, An Upper Bound for the Regularity of Ideals of Borel Type, 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, Computing bases of complete intersection rings in Noether position, Extended parallelism in the Gröbner basis algorithm, 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, Complexity of the word problem for commutative semigroups of fixed dimension, A new lower bound construction for commutative Thue systems with applications, Counting solutions to binomial complete intersections, Combinatorial dimension theory of algebraic varieties, Word problems over traces which are solvable in linear time, Generalised characteristic polynomials, The degree-complexity of the defining ideal of a smooth integral curve, Bouziane's transformation of the Petri net reachability problem and incorrectness of the related algorithm, Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states, The complexity of elementary algebra and geometry, Computer algebra: Past and future, The complexity of reachability in distributed communicating processes, The word and generator problems for lattices, Completeness results for conflict-free vector replacement systems, On the complexity of computing syzygies, Complexity of computations in Commutative Division of the USSR Academy of Sciences, Equations for the projective closure and effective Nullstellensatz, The membership problem for unmixed polynomial ideals is solvable in single exponential time, The complexity of problems involving structurally bounded and conservative Petri nets, Complexity of solution of linear systems in rings of differential operators, Decision problems for propositional linear logic, Computation of Hilbert functions, Normal and sinkless Petri nets, Notes on Gröbner bases, Complexity of deciding Tarski algebra, On the parallel complexity of the polynomial ideal membership problem, Trajectories of polynomial vector fields and ascending chains of polynomial ideals, Linear logic as a logic of computations, A solution to Kronecker's problem, Symmetry reductions and exact solutions of a class of nonlinear heat equations, Ideals generated by quadrics exhibiting double exponential degrees, The minimal components of the Mayr-Meyer ideals., Complexity bounds in elimination theory -- a survey., Algorithms for residues and Łojasiewicz exponents, Enumerating a subset of the integer points inside a Minkowski sum, Polynomial ideals for sandpiles and their Gröbner bases, A generic effective Nullstellensatz, Algebraic algorithms for sampling from conditional distributions, Triangular sets for solving polynomial systems: a comparative implementation of four methods, Solving degenerate sparse polynomial systems faster, Gröbner bases of toric varieties, A multiparameter analysis of the boundedness problem for vector addition systems, Projections of vector addition system reachability sets are semilinear, Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups., Computing a context-free grammar-generating series, A sharp bound for the Castelnuovo-Mumford regularity of subspace arrangements., On the embedded primes of the Mayr-Meyer ideals, Petri nets, Horn programs, linear logic and vector games, Linear logic automata, Binomial ideals, Fast theorem-proving and Wu's method, An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, Algorithmic aspects of Suslin's proof of Serre's conjecture, Weak Bézout inequality for D-modules, Comparison of theoretical complexities of two methods for computing annihilating ideals of polynomials, Bounds for the Castelnuovo-Mumford regularity of modules, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, On the complexity of reasoning in Kleene algebra, Effective Bezout identities in \({\mathbb{Q}}[z_ 1,\dots ,z_ n\)], Computational aspects of the coordinate ring of an algebraic variety, Annual Meeting of the Association for Symbolic Logic, Los Angeles, 1989, Residue currents with prescribed annihilator ideals, Classifying the computational complexity of problems, Fast Parallel Computation of Hermite and Smith Forms of Polynomial Matrices

Cites Work