La feuille des applications dites -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 -langages) sur partie algébrique, partie rationnelle (ou -langage) sur partie rationnelle. On étudie sous le nom de langage compilable les parties algébriques qu’une -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}, pages = {339--455}, publisher = {Institut Fourier}, address = {Grenoble}, volume = {18}, number = {1}, year = {1968}, doi = {10.5802/aif.287}, mrnumber = {38 #6909}, zbl = {0313.68065}, language = {fr}, url = {http://archive.numdam.org/articles/10.5802/aif.287/} }
TY - JOUR AU - Nivat, Maurice TI - Transductions des langages de Chomsky JO - Annales de l'Institut Fourier PY - 1968 SP - 339 EP - 455 VL - 18 IS - 1 PB - Institut Fourier PP - Grenoble UR - http://archive.numdam.org/articles/10.5802/aif.287/ DO - 10.5802/aif.287 LA - fr ID - AIF_1968__18_1_339_0 ER -
Nivat, Maurice. Transductions des langages de Chomsky. Annales de l'Institut Fourier, Tome 18 (1968) no. 1, pp. 339-455. doi : 10.5802/aif.287. http://archive.numdam.org/articles/10.5802/aif.287/
[1] On formal properties of simple phrase structure grammars in Y. Bar Hillel : Language and information, Addison Wesley Publishing Company (1964).
, , ,[2] Formal properties of grammars in Handbook of Mathematical Psychology, Wiley Publishing Company, New York 1963. | Zbl
,[3] The algebraic theory of context-free languages in Computer Programming and Formal systems, North Holland Publishing Company, Amsterdam 1963. | Zbl
, ,[4] Review of “A remark on finite transducers”, I.R.E. Trans Electronic Computers vol. EC II (1962) p. 802.
,[5] On relations defined by generalized finite automata, I.B.M. Journal of Research and development, vol. 9 (1965) p. 47-68. | MR | Zbl
et ,[6] Mathematical theory of context-free languages Mac Graw Hill Publishing Company, New York 1966. | MR | Zbl
,[7] Bounded Algol like languages, Trans American Math. Society, vol. 113 (1964) p. 333-368. | MR | Zbl
et ,[8] Deterministic Context-free languages, Information and Control, vol. (1966) p. 620-648. | MR | Zbl
et ,[9] 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 | Zbl
,[10] Structure of rings, American Mathematical Society, Providence 1956. | MR | Zbl
,[11] On the translation of languages from left to right, Information and Control, vol. 8 (1965) p. 607-639. | MR | Zbl
,[12] Combinatorial Group Theory, Interscience Publishing Company, New York 1966.
, , ,[13] Finite automata and the representation of events, Wright Air Development Command Technical Report n° 57-624 (1957) p. 112-137.
,[14] Report on the Algorithmic language Algol 60, Communications Assoc. Computing Machinery, vol. 3 (1960) p. 299-314. | MR | Zbl
, (edit),[15] Sur une classe de transducteurs, Séminaire Dubreil Pisot, 18ème 1964-1965. | Numdam | Zbl
,[16] 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 | Zbl
,[17] Sur l'irréductibilité de certaines représentations de monoïdes, C.R. Acad Sci. Paris, vol. 261 (1965) p. 2421-2422. | MR | Zbl
,[18] Progrès récents d'algèbre locale, Notas de matematica n° 19, Rio de Janeiro, (1959). | MR | Zbl
,[19] A remark on finite transducers, Information and Control, vol. 4 (1961) p. 185-196. | MR | Zbl
,[20] On the definition of a family of automata, Information and Control, vol. 4 (1961) p. 245-270. | MR | Zbl
,[21] On a theorem of R. Jungen, Proc. American Math. Society (1962) p. 189-197. | Zbl
,[22] Certain Elementary families of automata, in Proceedings of the symposium on mathematical theory of Automata, Polytechnic Institute of Brooklyn 1962.
,[23] Context-free languages and pushdown automata, Information and Control, vol. 6 (1963) p. 246-264. | Zbl
,[24] Sur certains sous-monoïdes libres, Bull. Société Math. France, vol. 93 (1965) p. 209-223. | Numdam | MR | Zbl
,[25] Un problème de la théorie des automates, Séminaire Dubreil-Pisot, 13ème année (1959-1960). | Numdam | Zbl
,[26] Mathematical models of languages, in Proceedings of the third IFIP Congress, New-York, (1965). | Zbl
,[27] 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] 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).
,Cité par Sources :