Transductions des langages de Chomsky

Maurice Nivat

Annales de l'institut Fourier (1968)

  • Volume: 18, Issue: 1, page 339-455
  • ISSN: 0373-0956

Abstract

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

How to cite

top

Nivat, Maurice. "Transductions des langages de Chomsky." Annales de l'institut Fourier 18.1 (1968): 339-455. <http://eudml.org/doc/73950>.

@article{Nivat1968,
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.},
author = {Nivat, Maurice},
journal = {Annales de l'institut Fourier},
language = {fre},
number = {1},
pages = {339-455},
publisher = {Association des Annales de l'Institut Fourier},
title = {Transductions des langages de Chomsky},
url = {http://eudml.org/doc/73950},
volume = {18},
year = {1968},
}

TY - JOUR
AU - Nivat, Maurice
TI - Transductions des langages de Chomsky
JO - Annales de l'institut Fourier
PY - 1968
PB - Association des Annales de l'Institut Fourier
VL - 18
IS - 1
SP - 339
EP - 455
AB - 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.
LA - fre
UR - http://eudml.org/doc/73950
ER -

References

top
  1. [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). Zbl0158.25307
  2. [2] N. CHOMSKY, Formal properties of grammars in Handbook of Mathematical Psychology, Wiley Publishing Company, New York 1963. Zbl0156.25303
  3. [3] N. CHOMSKY, MP. SCHUTZENBERGER, The algebraic theory of context-free languages in Computer Programming and Formal systems, North Holland Publishing Company, Amsterdam 1963. Zbl0148.00804
  4. [4] CC. ELGOLT, Review of “A remark on finite transducers”, I.R.E. Trans Electronic Computers vol. EC II (1962) p. 802. 
  5. [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. Zbl0135.00704MR35 #7732
  6. [6] S. GINSBURG, Mathematical theory of context-free languages Mac Graw Hill Publishing Company, New York 1966. Zbl0184.28401MR35 #2692
  7. [7] S. GINSBURG et E.H. SPANIER, Bounded Algol like languages, Trans American Math. Society, vol. 113 (1964) p. 333-368. Zbl0142.24803MR31 #5729
  8. [8] S. GINSBURG et Sheila A. GREIBACH, Deterministic Context-free languages, Information and Control, vol. (1966) p. 620-648. Zbl0145.00802MR34 #7301
  9. [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. Zbl0135.18404MR30 #2960
  10. [10] N. JACOBSON, Structure of rings, American Mathematical Society, Providence 1956. Zbl0073.02002MR18,373d
  11. [11] D.E. KNUTH, On the translation of languages from left to right, Information and Control, vol. 8 (1965) p. 607-639. Zbl0231.68027MR32 #7360
  12. [12] W. MAGNUS, A. KARRASS, D. SOLITAR, Combinatorial Group Theory, Interscience Publishing Company, New York 1966. 
  13. [13] J. MYHILL, Finite automata and the representation of events, Wright Air Development Command Technical Report n° 57-624 (1957) p. 112-137. 
  14. [14] P. NAUR, (edit), Report on the Algorithmic language Algol 60, Communications Assoc. Computing Machinery, vol. 3 (1960) p. 299-314. Zbl0089.12510MR24 #B485
  15. [15] M. NIVAT, Sur une classe de transducteurs, Séminaire Dubreil Pisot, 18ème 1964-1965. Zbl0189.02102
  16. [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. Zbl0208.45101MR39 #2513
  17. [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. Zbl0131.02002MR32 #1275
  18. [18] P. SAMUEL, Progrès récents d'algèbre locale, Notas de matematica n° 19, Rio de Janeiro, (1959). Zbl0228.16001MR26 #2458
  19. [19] MP. SCHUTZENBERGER, A remark on finite transducers, Information and Control, vol. 4 (1961) p. 185-196. Zbl0119.13901MR26 #1235
  20. [20] MP. SCHUTZENBERGER, On the definition of a family of automata, Information and Control, vol. 4 (1961) p. 245-270. Zbl0104.00702MR24 #B1725
  21. [21] MP. SCHUTZENBERGER, On a theorem of R. Jungen, Proc. American Math. Society (1962) p. 189-197. Zbl0107.03102
  22. [22] MP. SCHUTZENBERGER, Certain Elementary families of automata, in Proceedings of the symposium on mathematical theory of Automata, Polytechnic Institute of Brooklyn 1962. 
  23. [23] MP. SCHUTZENBERGER, Context-free languages and pushdown automata, Information and Control, vol. 6 (1963) p. 246-264. Zbl0148.25101
  24. [24] MP. SCHUTZENBERGER, Sur certains sous-monoïdes libres, Bull. Société Math. France, vol. 93 (1965) p. 209-223. Zbl0149.02601MR32 #7666
  25. [25] MP. SCHUTZENBERGER, Un problème de la théorie des automates, Séminaire Dubreil-Pisot, 13ème année (1959-1960). Zbl0113.01402
  26. [26] E. SHAMIR, Mathematical models of languages, in Proceedings of the third IFIP Congress, New-York, (1965). Zbl0201.33301
  27. [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. Zbl0165.02302
  28. [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). 

Citations in EuDML Documents

top
  1. Luc Boasson, Maurice Nivat, Transductions et familles de langages
  2. Luc Boasson, Familles de langages
  3. Robert Cori, Un langage quasi-rationnel lié aux graphes planaires
  4. Michel Fliess, Transductions algébriques
  5. J. M. Autebert, J. Beauquier, Une caractérisation des générateurs standard
  6. Jeannine Leguy, Transductions rationnelles décroissantes
  7. Michèle Soria, Une extension des langages déterministes
  8. Christian Choffrut, Sur les transductions reconnaissables
  9. A. Arnold, M. Dauchet, Théorie des magmoïdes
  10. J. L. Durieux, Sur l'image, par une transduction rationnelle, des mots sur une lettre

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.