Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups.

DOI10.1006/inco.1999.2812zbMath1046.68073OpenAlexW2036844537MaRDI QIDQ1854344

Ulla Koppenhagen, Ernst W. Mayr

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1999.2812

zbMATH Keywords

decision proceduresuniform word problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algebraic theory of languages and automata (68Q70) Thue and Post systems, etc. (03D03)

Related Items (1)

Complexity of Membership Problems of Different Types of Polynomial Ideals

Cites Work

• Unnamed Item
• 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
• The Complexity of the Finite Containment Problem for Petri Nets

This page was built for publication: Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups.