A bialgebraic approach to automata and formal language theory (Q408529): Difference between revisions

The concepts of algebra, coalgebra, and bialgebra based on a commutative ring are well-known in the literature. In this paper they are generalized to commutative semirings \(K\) in order to establish a close connection to automata and formel language theory. For this purpose \(K\)-semimodules, \(K\)-algebras, \(K\)-coalgebras and \(K\)-bialgebras are studied showing similar properties as in the classical case. Moreover \(K\)-linear automata are introduced, consisting of a \(K\)-semimodule with state vector and observation function, and the accepted language as behaviour of a \(K\)-linear automaton. As usual two automata are called equivalent, if they have the same behaviour. Together with suitable automata morphisms they define the category of \(K\)-linear automata. Similar to the classical case automata morphisms can be shown to preserve equivalence of the corresponding automata. One of the main results of the paper shows that there is an adjunction in the sense of adjoint functors between the categories of \(K\)-linear and classical deterministic automata. Using this adjunction and the well-known fact that equivalent minimal deterministic automata are isomorphic the following result is shown: Each pair of equivalent \(K\)-linear automata can be connected by an alternating sequence of automata morphisms. This allows to characterize equivalence of \(K\)-linear automata by the existence of connecting automata morphisms. Altogether the paper has established an interesting connnection between \(K\)-algebras and \(K\)-automata on one hand and \(K\)-coalgebras and formal languages on the other hand. However, generating grammars for formal languages are not considered.