Formal Languages and Automata V: Conway Semiring-Semimodule Pairs and Finite Automata
- DOI
- 10.5922/2223-2095-2009-10-1
- Pages
- 6-41
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.
Reference
5. Bloom St. L., Esik Z. Iteration theories. EATCS Monographs on Theoretical Computer Science. Springer, 1993.
6. Buechi J. R. On a decision method in restricted second order arithmetic //Proc. Int. Congr. Logic, Methodology and Philosophy of Science. 1962. P. 111.
7. Conway J. H. Regular algebra and nite machines. Chapman & Hall, 1971.
8. Elgot C. Matricial theories // J. Algebra. 1976. N 42. P. 391422.
9. Esik Z., Kuich W. Inductive ¤-semirings // Theoretical Computer Science.2004. N 324. P. 333.
10. Esik Z., Kuich W. On iteration semiring-semimodule pairs // Semigroup Forum. 2007. N 75. P. 129159.
11. Esik Z., Kuich W. A semiring-semimodule generalization of !-regular languages II // Journal of Automata, Languages and Combinatorics. 2005. N 10.P. 243264.Î