Tuesday, June 11, 2019 2:30 pm - 2:30 pm EDT
Sylvie Davis, Department of Pure Mathematics, University of Waterloo
"Monoids, Computation, and the State Complexity of Regular Languages"
The state complexity of regular languages is an active area of research in theoretical computer science. A regular language is a set of words such that a computer program with finite memory can determine whether or not a word belongs to the language. Such programs are said to "recognize" the language. The state complexity of a regular language is a measure of the amount of memory required to recognize the language, with respect to a specific state-based model of computation called a deterministic finite automaton. We will explore the relationship between finite-memory computation and abstract algebra, and show how reinterpreting deterministic finite automata as monoid actions allows us to attack problems in state complexity.