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