Details:
Title  Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups  Author(s)  Ulla Koppenhagen, Ernst W. Mayr  Type  Article in Journal  Abstract  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 $2^c cdots
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 $2^c  Length  27 
URL 
http://dx.doi.org/10.1006/inco.1999.2812 
Language  English  Journal  Inf.~Comput.  Volume  158  Number  2  Pages  98124  Publisher  Academic Press: Orlando  Year  2000  Editor  Meyer, Albert R.  Translation 
No  Refereed 
No 
