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

Ulla Koppenhagen, Ernst W. Mayr

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

5 Zitate (Scopus)

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.

OriginalspracheEnglisch
TitelFundamentals of Computation Theory - 11th International Symposium, FCT 1997, Proceedings
Redakteure/-innenBogdan S. Chlebus, Ludwik Czaja
Herausgeber (Verlag)Springer Verlag
Seiten257-268
Seitenumfang12
ISBN (Print)3540633863, 9783540633860
DOIs
PublikationsstatusVeröffentlicht - 1997
Veranstaltung11th International Symposium on Fundamentals of Computation Theory, FCT 1997 - Krakow, Polen
Dauer: 1 Sept. 19973 Sept. 1997

Publikationsreihe

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band1279
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Konferenz

Konferenz11th International Symposium on Fundamentals of Computation Theory, FCT 1997
Land/GebietPolen
OrtKrakow
Zeitraum1/09/973/09/97

Fingerprint

Untersuchen Sie die Forschungsthemen von „The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren