Talk:Krohn–Rhodes theory

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)

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)

---

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)

{{copyedit}}

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