logo ANNALES DE L'INSTITUT FOURIER

With cedram.org
Table of contents for this issue | Previous article
Maurice Nivat
Transductions des langages de Chomsky
Annales de l'institut Fourier, 18 no. 1 (1968), p. 339-455, doi: 10.5802/aif.287
Article PDF | Reviews MR 38 #6909 | Zbl 0313.68065

Résumé - Abstract

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.

Bibliography

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