Formal Languages and Automata V: Conway Semiring-Semimodule Pairs and Finite Automata
Abstract
This is the fth paper of a series of papers that will give a survey on several topics on formal languages and automata by using semirings, formal power series, matrices and xed point theory. The fth paper of this series deals with the basic results in the theory of nite automata over quemirings generalizing the classical nite automata accepting nite and in nite words. The presentation of these results is based on semiring-semimodule pairs, especially on Conway semiring-semimodule pairs. A Conway semiring-semimodule pair is a pair consisting of a
Conway semiring and a semimodule that satis es the sum-omega equation and the product-omega equation. We de ne these Conway
semiring-semimodule pairs and state some of their important properties. Then we introduce nite automata over quemirings and prove a Kleene Theorem. Furthermore, we introduce linear systems over quemirings as a generalization of regular grammars with nite and in nite derivations, and connect certain solutions of these linear systems with the behavior of nite automata over quemirings.