TY - JOUR

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

AU - Koppenhagen, Ulla

AU - Mayr, Ernst W.

PY - 2000

Y1 - 2000

N2 - In this paper, we present decision procedures for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups. These procedures require at most space 2c·n, where n is the size of the problem instance, and c is some problem independent constant. Furthermore, we show that the exponential space hardness of the above problems follows from the work of Mayr and Meyer. Thus, the presented algorithms are space optimal. Our results close the gap between the 2c′·n·log n space upper bound, shown by Rackoff for the coverability problem and shown by Huynh for the containment and the equivalence problems, and the exponential space lower bound resulting from the corresponding bound for the uniform word problem established by Mayr and Meyer.

AB - In this paper, we present decision procedures for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups. These procedures require at most space 2c·n, where n is the size of the problem instance, and c is some problem independent constant. Furthermore, we show that the exponential space hardness of the above problems follows from the work of Mayr and Meyer. Thus, the presented algorithms are space optimal. Our results close the gap between the 2c′·n·log n space upper bound, shown by Rackoff for the coverability problem and shown by Huynh for the containment and the equivalence problems, and the exponential space lower bound resulting from the corresponding bound for the uniform word problem established by Mayr and Meyer.

UR - http://www.scopus.com/inward/record.url?scp=0034191841&partnerID=8YFLogxK

U2 - 10.1006/inco.1999.2812

DO - 10.1006/inco.1999.2812

M3 - Article

AN - SCOPUS:0034191841

SN - 0890-5401

VL - 158

SP - 98

EP - 124

JO - Information and Computation

JF - Information and Computation

IS - 2

ER -