Transductions des langages de Chomsky

Nivat, Maurice

Annales de l'Institut Fourier, Tome 18 (1968) no. 1, pp. 339-455

La feuille des applications dites $K$-transductions, et qu’il serait légitime d’appeler applications rationnelles, d’un monoïde libre dans un autre monoïde est étudiée de façon systématique. L’intérêt de ces applications vient de ce qu’elles transportent partie algébrique (ou $C$-langages) sur partie algébrique, partie rationnelle (ou $K$-langage) sur partie rationnelle. On étudie sous le nom de langage compilable les parties algébriques qu’une $K$-transduction univoque applique dans un ensemble de Dyck (noyau d’un homomorphisme dans un groupe libre). On introduit la structure associative nouvelle de produit sélectif, aussitôt utilisée à la démonstration de l’équivalence de divers automates.

[1] Y. Bar Hillel, M. Perles, E. Shamir, On formal properties of simple phrase structure grammars in Y. Bar Hillel : Language and information, Addison Wesley Publishing Company (1964).

[2] N. Chomsky, Formal properties of grammars in Handbook of Mathematical Psychology, Wiley Publishing Company, New York 1963. | Zbl

[3] N. Chomsky, Mp. Schutzenberger, The algebraic theory of context-free languages in Computer Programming and Formal systems, North Holland Publishing Company, Amsterdam 1963. | Zbl

[4] Cc. Elgolt, Review of “A remark on finite transducers”, I.R.E. Trans Electronic Computers vol. EC II (1962) p. 802.

[5] Cc. Elgot et Je. Mezei, On relations defined by generalized finite automata, I.B.M. Journal of Research and development, vol. 9 (1965) p. 47-68. | Zbl | MR

[6] S. Ginsburg, Mathematical theory of context-free languages Mac Graw Hill Publishing Company, New York 1966. | Zbl | MR

[7] S. Ginsburg et E.H. Spanier, Bounded Algol like languages, Trans American Math. Society, vol. 113 (1964) p. 333-368. | Zbl | MR

[8] S. Ginsburg et Sheila A. Greibach, Deterministic Context-free languages, Information and Control, vol. (1966) p. 620-648. | Zbl | MR

[9] Sheila A. Greibach, A new normal form theorem for Context-free phrase structure grammars. Journal of the Association for computing machinery, vol. 12 (1965) p. 42-52. | Zbl | MR

[10] N. Jacobson, Structure of rings, American Mathematical Society, Providence 1956. | Zbl | MR

[11] D.E. Knuth, On the translation of languages from left to right, Information and Control, vol. 8 (1965) p. 607-639. | Zbl | MR

[12] W. Magnus, A. Karrass, D. Solitar, Combinatorial Group Theory, Interscience Publishing Company, New York 1966.

[13] J. Myhill, Finite automata and the representation of events, Wright Air Development Command Technical Report n° 57-624 (1957) p. 112-137.

[14] P. Naur, (edit), Report on the Algorithmic language Algol 60, Communications Assoc. Computing Machinery, vol. 3 (1960) p. 299-314. | Zbl | MR

[15] M. Nivat, Sur une classe de transducteurs, Séminaire Dubreil Pisot, 18ème 1964-1965. | Zbl | Numdam

[16] M. Nivat, Eléments de la théorie générale des codes, In Automata Theory (cours de l'école d'été de Ravello 1964), Academic Press New York 1966. | Zbl | MR

[17] M. Nivat, Sur l'irréductibilité de certaines représentations de monoïdes, C.R. Acad Sci. Paris, vol. 261 (1965) p. 2421-2422. | Zbl | MR

[18] P. Samuel, Progrès récents d'algèbre locale, Notas de matematica n° 19, Rio de Janeiro, (1959). | Zbl | MR

[19] Mp. Schutzenberger, A remark on finite transducers, Information and Control, vol. 4 (1961) p. 185-196. | Zbl | MR

[20] Mp. Schutzenberger, On the definition of a family of automata, Information and Control, vol. 4 (1961) p. 245-270. | Zbl | MR

[21] Mp. Schutzenberger, On a theorem of R. Jungen, Proc. American Math. Society (1962) p. 189-197. | Zbl

[22] Mp. Schutzenberger, Certain Elementary families of automata, in Proceedings of the symposium on mathematical theory of Automata, Polytechnic Institute of Brooklyn 1962.

[23] Mp. Schutzenberger, Context-free languages and pushdown automata, Information and Control, vol. 6 (1963) p. 246-264. | Zbl

[24] Mp. Schutzenberger, Sur certains sous-monoïdes libres, Bull. Société Math. France, vol. 93 (1965) p. 209-223. | Zbl | MR | Numdam

[25] Mp. Schutzenberger, Un problème de la théorie des automates, Séminaire Dubreil-Pisot, 13ème année (1959-1960). | Zbl | Numdam

[26] E. Shamir, Mathematical models of languages, in Proceedings of the third IFIP Congress, New-York, (1965). | Zbl

[27] E. Shamir, A representation theorem for algebraic and context-free power series in non commuting variates dans Arhib (ed.). Algebraic theory of machines, languages and semi-groups - Academic Press. | Zbl

[28] D.H. Younger, Recognition and parsing of Context-free languages in time n° 3 rapport n° 66-C-008, G, General Electric research and Development center, Schenectady (New-York).