MIT Libraries logoDSpace@MIT

MIT
View Item 
  • DSpace@MIT Home
  • Computer Science and Artificial Intelligence Lab (CSAIL)
  • LCS Publications
  • LCS Technical Memos (1974 - 2003)
  • View Item
  • DSpace@MIT Home
  • Computer Science and Artificial Intelligence Lab (CSAIL)
  • LCS Publications
  • LCS Technical Memos (1974 - 2003)
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Computational Complexity of the Word Problem for Commutative Semigroups

Author(s)
Cardoza, Edward W.
Thumbnail
DownloadMIT-LCS-TM-067.pdf (11.00Mb)
Advisor
Meyer, Albert R.
Metadata
Show full item record
Abstract
We analyze the computational complexity of some decision problems for commutative semigroups in terms of time and space on a Turing machine. The main result we present is that any decision procedure for the word problemm for commutative semigroups requires storage space at least proportional to n/logn on a multitape Turing machine. This implies that the word problem is polynomia space hard (and in particular that it is at least NP-hard). We comment on the close relation of commutative semigroups to vector addition systems and Petri nets. We also show that the lower bound of space n/logn can be extended to certain other natural algorithmic problems for commutative semigroups. Finally we show that for several other algorithmic problems for commutative semigroups there exist polynomial time algorithms.
Date issued
1975-10
URI
https://hdl.handle.net/1721.1/148895
Series/Report no.
MIT-LCS-TM-067MAC-TM-067

Collections
  • LCS Technical Memos (1974 - 2003)
  • MAC Memos (1963 - 1974)

Browse

All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

Login

Statistics

OA StatisticsStatistics by CountryStatistics by Department
MIT Libraries
PrivacyPermissionsAccessibilityContact us
MIT
Content created by the MIT Libraries, CC BY-NC unless otherwise noted. Notify us about copyright concerns.