Quasitriangular Structure of Myhill–Nerode Bialgebras

In computer science the Myhill–Nerode Theorem states that a set L of words in a finite alphabet is accepted by a finite automaton if and only if the equivalence relation ～L, defined as x ～L y if and only if xz ∈ L exactly when yz ∈ L, ？z, has finite index. The Myhill–Nerode Theorem can be generalized to an algebraic setting giving rise to a collection of bialgebras which we call Myhill–Nerode bialgebras. In this paper we investigate the quasitriangular structure of Myhill–Nerode bialgebras.