Talk:Krohn–Rhodes theory

This article is within the scope of WikiProject Requested articles, because it is used for the administration of the Requested articles process or it was formerly listed at Requested articles.Requested articlesWikipedia:WikiProject Requested articlesTemplate:WikiProject Requested articlesRequested articles

Mathematics Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Low	This article has been rated as Low-priority on the project's priority scale.

The article is incorrect. John Rhodes proved that semigroup complexity for a finite semigroup is indeed decidable. The following link to an invitation to a year 2000 seminar entitled "Techniques in my Proof that Complexity is Decidable for Finite Automata and Semigroups" given in Hungary should suffice as evidence: http://atlas-conferences.com/c/a/e/c/44.htm

I took a course from John Rhodes, and while he didn't describe the algorithm he did say that he got the idea for it while vacationing at the Horizons Casino in Stateline, NV (on the shores of Lake Tahoe). The algorithm is reportedly so complex that an ackermann function, one of the fastest growing functions known to man, describes the runtime as a function of input complexity.

The proof I think you are referring to was incorrect (as is now acknowledged by Rhodes himself). It relied upon on a published theorem of some other authors (who shall remain nameless), the proof of which turned out to have an error in it. Rhodes is still working on this problem and I understand has another idea for how decidability can be proved, but this has not yet been published or peer-reviewed. Best wishes, Cambyses 08:11, 20 March 2006 (UTC)[reply]

Thanks that's very current information. I stand corrected. -- skyscrapes

That's okay. It's good to know these relatively obscure articles are being checked by people who are actually familiar with the subjects! Best wishes, Cambyses 07:54, 24 March 2006 (UTC)[reply]

Question. The article says "In fact, there are semigroups of every non-negative integer complexity. For example, for any n greater than 1, the multiplicative semigroup of all (n+1)×(n+1) upper triangular matrices over any fixed finite field has complexity n".

What about commutative finite semigroups with regards to the complexity? Any examples?

They all have complexity 1 since they decompose as a direct product of an Abelian group and a commutative aperiodic. 21:33, 23 May 2007 (UTC)

Link to wreath product

Wreath product on this page links to group theory wreath product. That's not the same as the one for S-acts! VasileGaburici (talk) 02:28, 15 September 2008 (UTC)[reply]

This article discusses history and applications but is thin on mathematical details. VasileGaburici (talk) 02:32, 15 September 2008 (UTC)[reply]

Link to wreath product

{{copyedit}}