The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups

DOI10.1007/BFb0036189MaRDI QIDQ5055940

Ernst W. Mayr, Ulla Koppenhagen

Publication date: 9 December 2022

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Commutative semigroups (20M14)

Related Items

On polynomial ideals, their complexity, and applications ⋮ An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, and applications to commutative semigroups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The equality problem for vector addition systems is undecidable
• The covering and boundedness problems for vector addition systems
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Rational sets in commutative monoids
• Some algorithmic problems for finitely defined commutative semigroups
• The Structure of Polynomial Ideals and Gröbner Bases
• Admissible orders and linear forms