Event Type:

Lonseth Lecture

Date/Time:

Friday, April 19, 2019 - 17:00 to 17:50

Location:

CH2M Hill Alumni Center, Willamette Room

Event Link:

Guest Speaker:

Institution:

Laboratoire J.A. Dieudonné, Université Côte d’Azur, France

Abstract:

Automata are very simple computational models. They are important in applications of computer science but also serve as a laboratory for studying the complexity of algorithms. In this talk we introduce automata and show how finite monoids, certain very abstract algebraic structures, may be assigned as invariants of automata. We illustrate how these invariants are powerful enough to make deep computational questions decidable. Finally we give a glimpse of an idea how this can be generalized to provide sophisticated mathematical tools for the study of computational complexity classes.

As is traditional, the Lonseth lecture will be preceded by the Department of Mathematics annual awards ceremony at 4:30pm. The Lonseth lecture will be followed by a reception in the Trysting Tree Room at 6pm.