# Formal Languages and Automata VI:-algebraic systems and transducers

Author |
Aleshnikov S. I., Boltnev Yu. F., Ã‰sik Z., Ishanov S. A., Kuich W. |

Pages |
8-32 |

Article |
Download |

Keywords |
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 (summary) |
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. |

References |
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.
20. Perrin D., Pin J.-E. Innite Words. Elsevier, 2004. |

Back to the section