Formal Languages and Automata VI:-algebraic systems and transducers :: IKBFU's united scientific journal editorial office

×

Login
Password
Forgot your password?
Login As
You can log in if you are registered at one of these services:
   
There are no complicated sciences, there are only complicated interpretations
Alexader Herzen

DOI-generator Search by DOI on Crossref.org

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.
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.


Back to the section