|
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. |