Formal Languages and Automata V: Conway Semiring-Semimodule Pairs and Finite Automata :: IKBFU's united scientific journal editorial office


Forgot your password?
Login As
You can log in if you are registered at one of these services:
There is only one science. Two sciences are impossible as two universes are
Alexander Herzen

DOI-generator Search by DOI on

Formal Languages and Automata V: Conway Semiring-Semimodule Pairs and Finite Automata

Author Aleshnikov S. I., Boltnev Yu. F., Ésik Z., Ishanov S. A., Kuich W.
DOI 10.5922/2223-2095-2009-10-1
Pages 6-41
Article Download
Keywords formal languages, automata, semiring, formal power series, matrix,xed point.
Abstract (summary) 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 innite 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 satises the sum-omega equation and the product-omega equation. We dene 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 innite derivations, and connect certain solutions of these linear systems with the behavior of nite automata over quemirings.
References 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.Î

Back to the section