Transductions des langages de Chomsky
Nivat, Maurice
Annales de l'Institut Fourier, Tome 18 (1968), p. 339-455 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

@article{AIF_1968__18_1_339_0,
     author = {Nivat, Maurice},
     title = {Transductions des langages de Chomsky},
     journal = {Annales de l'Institut Fourier},
     volume = {18},
     year = {1968},
     pages = {339-455},
     doi = {10.5802/aif.287},
     mrnumber = {38 \#6909},
     zbl = {0313.68065},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/AIF_1968__18_1_339_0}
}

Nivat, Maurice. Transductions des langages de Chomsky. Annales de l'Institut Fourier, Tome 18 (1968) pp. 339-455. doi : 10.5802/aif.287. http://gdmltest.u-ga.fr/item/AIF_1968__18_1_339_0/

[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 0156.25303

[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 0148.00804

[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. | MR 35 #7732 | Zbl 0135.00704

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

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

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

[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. | MR 30 #2960 | Zbl 0135.18404

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

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

[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. | MR 24 #B485 | Zbl 0089.12510

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

[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. | MR 39 #2513 | Zbl 0208.45101

[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. | MR 32 #1275 | Zbl 0131.02002

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

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

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

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

[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 0148.25101

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

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

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

[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 0165.02302

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