Search
Submit an article RU
Physics, mathematics, and technology

2010 Issue №10

Back to the list Download the article
Aleshnikov S. I. Boltnev Yu. F. Ésik Z. Ishanov S. A. Kuich W.

Formal Languages and Automata VI:-algebraic systems and transducers

Pages
8-32
formal languages automata semiring formal power series, matrix xed point !-algebraic system !-algebraic power series !-contextfree grammar !-context-free language transducer rational transducer algebraic transducer transductions over starsemiringomegasemimodule pair.

Abstract

This is the sixth 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 andxed point theory. The sixth paper of this series deals with the basic results in the theory of !-algebraic systems over quemirings generalizing the classical context-free grammars generating languages overnite and innite words. The presentation of these results is based on continuous starsemiring-omegasemimodule pairs. We dene !-algebraic systems and characterize their solutions
of order k by behaviors of algebraic nite automata. These solutions are then set in correspondence to !-context-free languages. Then we introduce rational and algebraic transducers, and abstract !-families of power series over quemirings and prove that rational and algebraic power series of nite and innite words constitute such abstract !-families of power series.

Reference

6. Berstel J. Transductions and Context-Free Languages.

7. Bloom St. L.,  Esik Z. Iteration Theories. EATCS Monographs on Theoretical Computer Science. Springer, 1993.

8. Bychi J. R. On a decision method in restricted second order arithmetic // Proc. Int. Congr. Logic, Methodology and Philosophy of Science, 1960. Stanford University Press, 1962. P. 111.

9. Cohen R. S., Gold A. Y. Theory of !-languages I: Characterizations of !-context-free languages // JCSS. 15(1977). P. 169184.
10. Conway J. H. Regular Algebra and Finite Machines. Chapman & Hall,1971.
11. Droste M., Kuske D. Skew and innitary formal power series. ICALP 2003, LNCS. 2719(2003). P. 426438.
12. Elgot C. Matricial theories // J. Algebra. 42(1976). P. 391422.
13.  Esik Z., Kuich W. Inductive ¤-semirings // Theoretical Computer Science. 324(2004). P. 3-33.
14.  Esik Z., Kuich W. A semiring-semimodule generalization of !-contextfree languages // LNCS. 3113(2004). P. 6880.
15.  Esik Z., Kuich W. On iteration semiring-semimodule pairs //Semigroup Forum. 75(2007). P. 129159.
16.  Esik Z., Kuich W. A semiring-semimodule generalization of !-regular languages II // Journal of Automata, Languages and Combinatorics. 10(2005).P. 243264.
17.  Esik Z., Kuich W. A semiring-semimodule generalization of transducers and abstract !-families of power series // Ibid. 12(2007). P. 435454.
18. Kuich W., Salomaa A. Semirings, Automata, Languages // EATCS Monographs on Theoretical Computer Science. Vol. 5. Springer, 1986.
19. Lausch H., Nobauer W. Algebra of Polynomials. North-Holland, 1973.

20. Perrin D., Pin J.-E. Innite Words. Elsevier, 2004.