Algebraic Myhill-Nerode Theorems

摘要

The Myhill-Nerode Theorem states that the equivalence relation ～_L given by a language L has finite index if and only if L is accepted by a finite automaton. In this paper we give several generalizations of the theorem which are algebraic in nature. In our versions, a finiteness condition involving the action of a semigroup on a certain function plays the role of the finiteness of the index of ～_L, while various algebraic structures including algebras, coalgebras, and bialgebras play the role of the finite automaton which accepts the language. We develop additional theory concerning the algebraic objects which so arise, and study the minimal ones.