Rationality in Algebras with a Series Operation

摘要

We consider the notion of rationality in algebras with a designated binary associative operation called the series operation, or the sequential product. We define automata operating in these algebras and rational expressions matching their expressive power, and we show that this expressive power equals that of algebraic recognizability. The framework which we consider encompasses both the free semigroup and the term algebras and the restriction of our results to these special cases coincides exactly with the classical results on recognizability (Kleene, Myhill, and Nerode for work languages, and Thatcher and Weight for term languages).