Tata Institute of Fundamental Research
50 Years of the Krohn-Rhodes Theorem
Seminar
Speaker:
Kamal Lodaya (Institute of Mathematical Sciences
Department of Computer Science
CIT Campus
Chennai 600113)
Organiser:
Paritosh K Pandya
Date:
Wednesday, 12 Jun 2013, 11:00 to 12:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
A little over 50 years ago (1962), we had the first nontrivial theorem which used an algebraic approach to automata theory: Schuetzenberger's theorem giving an algorithm to check whether a given regular language is definable using a starfree expression. The same year saw the announcement of the extension of the classification of finite groups to finite semigroups: the Krohn-Rhodes theorem showing that the semigroups which are groupfree can be composed using just one three-element "prime", the remaining primes being the finite simple groups. The journal paper appeared in 1965. (The complexity of this decomposition remains open.) In 1997, a new proof was found for Schuetzenberger's theorem. Recently this has led to new proofs for the Krohn-Rhodes theorem. It would be too much to pack all this into one talk, so we will give an overview, and explain all the required algebra.
| Speaker: | Kamal Lodaya (Institute of Mathematical Sciences Department of Computer Science CIT Campus Chennai 600113) |
| Organiser: | Paritosh K Pandya |
| Date: | Wednesday, 12 Jun 2013, 11:00 to 12:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
A little over 50 years ago (1962), we had the first nontrivial theorem which used an algebraic approach to automata theory: Schuetzenberger's theorem giving an algorithm to check whether a given regular language is definable using a starfree expression. The same year saw the announcement of the extension of the classification of finite groups to finite semigroups: the Krohn-Rhodes theorem showing that the semigroups which are groupfree can be composed using just one three-element "prime", the remaining primes being the finite simple groups. The journal paper appeared in 1965. (The complexity of this decomposition remains open.) In 1997, a new proof was found for Schuetzenberger's theorem. Recently this has led to new proofs for the Krohn-Rhodes theorem. It would be too much to pack all this into one talk, so we will give an overview, and explain all the required algebra.