The complexity of the word problems for commutative semigroups and polynomial ideals

Ernst W. Mayr; Albert R. Meyer

doi:10.1016/0001-8708(82)90048-2

The complexity of the word problems for commutative semigroups and polynomial ideals

Ernst W. Mayr, Albert R. Meyer

Massachusetts Institute of Technology

Publikation: Beitrag in Fachzeitschrift › Artikel › Begutachtung

359 Zitate (Scopus)

Abstract

Any decision procedure for the word problems for commutative semigroups and polynomial deals inherently requires computational storage space growing exponentially with the size of the problem instance to which the procedure is applied. This bound is achieved by a simple procedure for the semigroup problem.

Originalsprache	Englisch
Seiten (von - bis)	305-329
Seitenumfang	25
Fachzeitschrift	Advances in Mathematics
Jahrgang	46
Ausgabenummer	3
DOIs	https://doi.org/10.1016/0001-8708(82)90048-2
Publikationsstatus	Veröffentlicht - Dez. 1982
Extern publiziert	Ja

Zugriff auf Dokument

10.1016/0001-8708(82)90048-2

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

@article{c3b604c4cc47496eaf59572d68ef9acf,

title = "The complexity of the word problems for commutative semigroups and polynomial ideals",

abstract = "Any decision procedure for the word problems for commutative semigroups and polynomial deals inherently requires computational storage space growing exponentially with the size of the problem instance to which the procedure is applied. This bound is achieved by a simple procedure for the semigroup problem.",

author = "Mayr, {Ernst W.} and Meyer, {Albert R.}",

year = "1982",

month = dec,

doi = "10.1016/0001-8708(82)90048-2",

language = "English",

volume = "46",

pages = "305--329",

journal = "Advances in Mathematics",

issn = "0001-8708",

publisher = "Academic Press Inc.",

number = "3",

}

TY - JOUR

T1 - The complexity of the word problems for commutative semigroups and polynomial ideals

AU - Mayr, Ernst W.

AU - Meyer, Albert R.

PY - 1982/12

Y1 - 1982/12

N2 - Any decision procedure for the word problems for commutative semigroups and polynomial deals inherently requires computational storage space growing exponentially with the size of the problem instance to which the procedure is applied. This bound is achieved by a simple procedure for the semigroup problem.

AB - Any decision procedure for the word problems for commutative semigroups and polynomial deals inherently requires computational storage space growing exponentially with the size of the problem instance to which the procedure is applied. This bound is achieved by a simple procedure for the semigroup problem.

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

U2 - 10.1016/0001-8708(82)90048-2

DO - 10.1016/0001-8708(82)90048-2

M3 - Article

AN - SCOPUS:0001751788

SN - 0001-8708

VL - 46

SP - 305

EP - 329

JO - Advances in Mathematics

JF - Advances in Mathematics

IS - 3

ER -

The complexity of the word problems for commutative semigroups and polynomial ideals

Abstract

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Dieses zitieren