Olivetti Club

Luke Serafin
Morita Equivalence for Kleene Algebra

Tuesday, September 17, 2024 - 4:30pm
Malott 406

Kleene algebrae are additively-idempotent semirings with additional structure which enables them to naturally describe processes which change state. The most famous Kleene algebra is the algebra of regular expressions over a finite alphabet, which is used for pattern matching in computer science. Elements of Kleene algebrae may also be regarded as nondeterministic programs that specify at each stage what changes to the current state are allowed. With this interpretation they are versatile tools for verifying the correctness of computer programs. Matrices encode automata over Kleene algebrae, and we show that Morita-equivalent Kleene algebrae have equivalent categories of automata. Along the way we define Kleene modules and their tensor products. Time permitting we shall look at some applications of these.