Home | People | Seminar | Conferences | Resources


Title: Determining the complexity of finite state machine

Abstract: One of the basic mathematical models of computation is a finite state machine called an automaton. Automata are finite directed graphs (with multiple edges and loops allowed) whose edges are labeled by a finite alphabet and with specified vertices where you are allowed to start and end. In this talk I will discuss one measure of the complexity of such a machine based on wreath products. This is called the Krohn-Rhodes complexity of an autamaton. For thirty years, it has been conjectured that given a finite state machine, its Krohn-Rhodes complexity is decidable. This conjecture has recently been proved and I will present a nice geometric construction which was used in the solution.

Return to the seminar page.

Home | People | Seminar | Conferences | Resources

Please send comments about this page to Maurice Rojas at rojas@math.tamu.edu.
Last Modified on 15/Sep/99