@inproceedings{779b8594b6a24688b8b255d118689f45,
title = "The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups",
abstract = "In this paper, we present optimal decision procedures for the coverability, 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. Our results close the gap between the 2C1.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.",
author = "Ulla Koppenhagen and Mayr, {Ernst W.}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 11th International Symposium on Fundamentals of Computation Theory, FCT 1997 ; Conference date: 01-09-1997 Through 03-09-1997",
year = "1997",
doi = "10.1007/BFb0036189",
language = "English",
isbn = "3540633863",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "257--268",
editor = "Chlebus, {Bogdan S.} and Ludwik Czaja",
booktitle = "Fundamentals of Computation Theory - 11th International Symposium, FCT 1997, Proceedings",
}