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

Research output: Contribution to journal › Article › peer-review

353 Scopus citations

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.

Original language	English
Pages (from-to)	305-329
Number of pages	25
Journal	Advances in Mathematics
Volume	46
Issue number	3
DOIs	https://doi.org/10.1016/0001-8708(82)90048-2
State	Published - Dec 1982
Externally published	Yes

Access to Document

10.1016/0001-8708(82)90048-2

Cite this

@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

Access to Document

Other files and links

Fingerprint

Cite this