FG1 Seminar talk

2010-06-18
Zoltan Esik
Equational theories and finite automata

Abstract:
Conway invented a remarkable matrix calculus for finite automata that led to the notion of Conway semiring. Iteration semirings are Conway semirings satisfying Conway's group identities. The equational axioms of Conway semirings are sufficient for establishing Kleene's theorem in a general setting, and iteration semirings provide an equational basis for the behavioral equivalence of finite automata. Two automata are called equivalent if they represent the same rational power series. We describe semirings and semialgebras of rational power series as the free algebras in various varieties and quasi-varieties related to iteration semirings.