Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

An effective lower bound for group complexity of finite semigroups and automata


Authors: Karsten Henckell, John Rhodes and Benjamin Steinberg
Journal: Trans. Amer. Math. Soc. 364 (2012), 1815-1857
MSC (2010): Primary 20M07
Published electronically: November 8, 2011
MathSciNet review: 2869193
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The question of computing the group complexity of finite semigroups and automata was first posed in K. Krohn and J. Rhodes, Complexity of finite semigroups, Annals of Mathematics (2) 88 (1968), 128-160, motivated by the Prime Decomposition Theorem of K. Krohn and J. Rhodes, Algebraic theory of machines, I: Prime decomposition theorem for finite semigroups and machines, Transactions of the American Mathematical Society 116 (1965), 450-464. Here we provide an effective lower bound for group complexity.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 20M07

Retrieve articles in all journals with MSC (2010): 20M07


Additional Information

Karsten Henckell
Affiliation: Department of Mathematics/Computer Science, New College of Florida, 5800 Bay Shore Road, Sarasota, Florida 34243-2109
Email: KHenckell@ncf.edu

John Rhodes
Affiliation: Department of Mathematics, University of California at Berkeley, Berkeley, California 94720
Email: jrhodes@math.berkeley.edu

Benjamin Steinberg
Affiliation: School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario Canada K1S 5B6
Address at time of publication: Department of Mathematics, City College of New York, NAC 8/133, Convent Avenue at 138th Street, New York, New York 10031
Email: bsteinbg@math.carleton.ca, bsteinberg@ccny.cuny.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-2011-05379-1
PII: S 0002-9947(2011)05379-1
Keywords: Krohn-Rhodes complexity
Received by editor(s): December 4, 2008
Received by editor(s) in revised form: May 11, 2010
Published electronically: November 8, 2011
Additional Notes: The second and third authors gratefully acknowledge the support of NSERC and the Committee on Research of the Academic Senate of the University of California at Berkeley for their generous support.
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.