Transductions des langages de Chomsky. (French) Zbl 0313.68065


68Q45 Formal languages and automata


Full Text: DOI Numdam EuDML


[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). · Zbl 0158.25307
[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. · Zbl 0135.00704
[6] S. GINSBURG, Mathematical theory of context-free languages Mac Graw Hill Publishing Company, New York 1966. · Zbl 0184.28401
[7] S. GINSBURG et E.H. SPANIER, Bounded algol like languages, Trans American Math. Society, vol. 113 (1964) p. 333-368. · Zbl 0142.24803
[8] S. GINSBURG et Sheila A. GREIBACH, Deterministic context-free languages, Information and Control, vol. (1966) p. 620-648. · 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. · Zbl 0135.18404
[10] N. JACOBSON, Structure of rings, American Mathematical Society, Providence 1956. · 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. · Zbl 0231.68027
[12] W. MAGNUS, A. KARRASS, D. SOLITAR, Combinatorial group theory, Interscience Publishing Company, New York 1966. · Zbl 0138.25604
[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 0089.12510
[15] M. NIVAT, Sur une classe de transducteurs, Séminaire Dubreil Pisot, 18ème 1964-1965. · 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. · 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. · Zbl 0131.02002
[18] P. SAMUEL, Progrès récents d’algèbre locale, Notas de matematica n° 19, Rio de Janeiro, (1959). · Zbl 0228.16001
[19] MP. SCHUTZENBERGER, A remark on finite transducers, Information and Control, vol. 4 (1961) p. 185-196. · Zbl 0119.13901
[20] MP. SCHUTZENBERGER, On the definition of a family of automata, Information and Control, vol. 4 (1961) p. 245-270. · 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. · 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). · 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).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.