Les débuts de la théorie des automates
Séminaire de Philosophie et Mathématiques no. 1  (1993), p. 1-17
@article{SPHM_1993___1_A1_0,
     author = {Perrin, Dominique},
     title = {Les d\'ebuts de la th\'eorie des automates},
     journal = {S\'eminaire de Philosophie et Math\'ematiques},
     publisher = {IREM Paris-Nord},
     number = {1},
     year = {1993},
     pages = {1-17},
     language = {fr},
     url = {http://www.numdam.org/item/SPHM_1993___1_A1_0}
}
Perrin, Dominique. Les débuts de la théorie des automates. Séminaire de Philosophie et Mathématiques, no. 1 (1993), pp. 1-17. http://www.numdam.org/item/SPHM_1993___1_A1_0/

[1] Roy L. Adler, D. Coppersmith, and M. Hassner. Algorithms for sliding block codes. IEEE Trans. Inform. Theory, IT-29:5-22, 1983. | MR 711274 | Zbl 0499.94009

[2] Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman. Compilers, Principles, Techniques and Tools. Addison Wesley, 1986.

[3] Marie-Pierre Béal. Codage Symbolique. Masson, 1993.

[4] V. Belevitch. Summary of the history of circuit theory. Proc. IRE, 50:848 855, 1962.

[5] Jean Berstel and Dominique Perrin. Theory of Codes. Academic Press, 1985. | MR 797069 | Zbl 0587.68066

[6] Richard Büchi. Weak second order arithmetic and finite automata. Zeit. Math. Logik Grund., 6:66 92, 1960. | MR 125010 | Zbl 0103.24705

[7] Richard Büchi. On a decision method in restricted second order arithmetic. Int. Proc. 1960 Int. Congress on Logic, Methodology and Philosophy of Science, pages 1-11. Stanford University press, 1962. | MR 183636 | Zbl 0147.25103

[8] Noam Chomsky. Three models for the description of language. IRE Trans. Inf. Th., IT-2, 1956. (Proc. of the symposium on Information Theory, Sept. 1956). | Zbl 0156.25401

[9] Noam Chomsky. Syntactic Structures. Mouton, 1957.

[10] Alonzo Church. Application of recursive arithmetic to the problem of circuit synthesis. In Summaries of talks presented at the Summer Institute for Symbolic logic, pages 3 50. Cornell University, 1957. | Zbl 0206.47902

[11] Robert L. Constable. The role of finite automata in the development of modern computing theory. In K.Kunen J.Barwise, H.J.Keisler, editor, The Kleene symposium, pages 61 83. North Holland, 1980. | MR 591875 | Zbl 0468.68060

[12] John H. Conway. Regular Algebra and Finite Machines. Chapman and Hall, 1971. | Zbl 0231.94041

[13] Samuel Eilenberg. Automata, Languages and Machines, volume A. Academic Press, 1974. | MR 530382 | Zbl 0359.94067

[14] Samuel Eilenberg. Automata, Languages and Machines, volume B. Academic Press, 1976. | MR 530383 | Zbl 0359.94067

[15] Calvin C. Elgot. Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc., pages 21 51, 1961. | MR 139530 | Zbl 0111.01102

[16] E. N. Gilbert and E. F. Moore. Variable length binary encodings. Bell Systems Tech. J., 38:933-967, 1959. | MR 108413

[17] Andrew Gleason. Semigroups of shift register matrices. Mathematical Systems Theory, 25:253 267, 1992. (reproduction des notes d'un centre donné à Princeton en 1960). | MR 1166764 | Zbl 0790.20086

[18] Kurt Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandte Systeme I. Monatshefte für Mathematik und Physik, XXXVIII:173-198, 1931. | MR 1549910 | Zbl 0002.00101

[19] Sheila Greibach. Formal languages: origins and directions. Ann. Hist. Comput., 3, 1981. | MR 641890 | Zbl 0998.01515

[20] Maurice Gross and Dominique Perrin. Electronic Dictionnaries and Automata in Computational Linguistics. Lecture Notes in Computer Science, 377. Springer, 1989.

[21] Paul Halmos. Entropy in ergodic theory. In Selecta Expository Writing. Springer, 1983. (reproduction de notes de cours a l'Université de Chicago, 1959). | MR 692366

[22] G. Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Math. Syst. Theory, 3:320 375, 1969. | MR 259881 | Zbl 0182.56901

[23] John E. Hopcroft and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison Wesley, 1979. | MR 645539 | Zbl 0847.68065

[24] D. A. Huffman. A method for the construction of minimum redundancy codes. Proc. IRE, 40:1098-1101, 1951. | Zbl 0137.13605

[25] D. A. Huffman. The synthesis of sequential switching circuits. Journal of the Franklin Institute, 257:161-190, 1954. repris dans Sequential Machines, E.F.Moore ed.,Addison Wesley, 1964. | MR 62648 | Zbl 0166.27201

[26] David A Huffman. Canonical forms for information-lossless finite-state logical machines. In E. F. Moore, editor, Sequential Machines, Selected Papers. Addison Wesley, 1964. | Zbl 0166.26802

[27] A. Ya. Khinchine. Mathematical Foundations of Information Theory. Dover, 1957. | Zbl 0088.10404

[28] Stephen C. Kleene. Representation of events in nerve nets and finite automata. In C.E.Shannon and J.McCarthy, editors, Automata Studies, pages 3 42. Princeton University Press, 1956. | MR 77478

[29] Kenneth Krohn and John Rhodes. Algebraic theory of machines, I. Prime decomposition theorem for finite semigroups and machines. Trans. Amer. Math. Soc., 116:450 464, 1965. | MR 188316 | Zbl 0148.01002

[30] Gérard Lallement. Semigroups and Combinatorial Applications. Wiley, 1979. | MR 530552 | Zbl 0421.20025

[31] J. Van Lecuwen, editor. Handbook of Theoretical Computer Science. Elsevier, 1990. | MR 1127176

[32] Warren Mcculloch and Walter Pitts. A logical calculus of the ideas immanent in nervous activity. Bullettin of Mathematical Bophisics, 5:115 133, 1943. | MR 10388 | Zbl 0063.03860

[33] Robert Mcnaughton. The theory of automata, a survey. In F. L. Alt, editor, Advances in Computers, volume 2, pages 379-416. Academic Press, 1961. | MR 136487 | Zbl 0133.09801

[34] Robert Mcnaughton. testing and generating infinite sequences by a finite automaton. Information and Control, 9:521 530, 1966. | MR 213241 | Zbl 0212.33902

[35] Robert Mcnaughton and Seymour Papert. Counter-Free Automata. MIT Press, 1971. | MR 371538 | Zbl 0232.94024

[36] Yu. T. Medvedev. Sur la classe des événements représentables dans un automate fini(en russe). In Automaty, pages 385-401, 1956. trad.angl. in Sequential machines, E.F.Moore ed., Addison Wesley, 1964. | Zbl 0199.04202

[37] E.F. Moore, Gedanken experiments on sequential machines. In C. E. Shannon and J. McCarthy, editors, Automata Studies, pages 129 156. Princeton University Press, 1956. | MR 78059

[38] M. Morse and G. Hedlund. Symbolic dynamics. Amer. J. of Math., 3:286-303, 1936. | JFM 64.0798.04

[39] Marston Morse. Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc., 22:84 110, 1921. | JFM 48.0786.06 | MR 1501161

[40] Jean Mosconi. La constitution de la théorie des automates. Atelier National de Reproduction des Thèses, Université de Lille III, 9 rue A. Angellier 59046 Lille, 1989. 2 vol.

[41] David E. Muller. Infinite sequences and finite machines. In Switching circuit theory and logical design, pages 3-16. IEEE, 1963.

[42] Dominique Perrin. Finite automata. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, chapter 1, pages 1-57. Elsevier, 1990. | MR 1127186 | Zbl 0900.68312

[43] Dominique Perrin and Jacques Sakarovitch. Automates finis. In Journées scientifiques de l'UAP, 1989. | Numdam | Zbl 0543.68038

[44] Jean Eric Pin. Variétés de langages Formels. Masson, 1984. (Varieties of Formal languages, North Oxford Plenum, 1986). | Zbl 0636.68093

[45] Michael O. Rabin. Decidability of second-order structures and automata on infinite trees. Trans. Amer. Math. Soc., 141:1-35, 1969. | MR 246760 | Zbl 0221.02031

[46] Michael O. Rabin and Dana Scott. Finite automata and their decision problems. IBM journal of Research and developpement, 3:114-125, 1959. repris dans Sequential Machines, E.F.Moore ed., Addison Wesley, 1964. | MR 103795 | Zbl 0158.25404

[47] M. P. Schützenberger. Une théorie algébrique du codage. In Séminaire Dubreil-Pisot, 1955. exposé n!15.

[48] M.P. Schützenberger. On monoids having only trivial subgroups. Information and Control, 8:190-194, 1965. | MR 176883 | Zbl 0131.02001

[49] C.E. Shannon. A symbolic analysis of relay and switching circuits. Trans. Amer. Inst. Electrical Engineers, 57:713-723, 1938.

[50] Claude E. Shannon. A mathematical theory of communication. Bell Systems Tech. Journal, XXVII:379-423, 623-656, 1948. (reproduit dans The mathematical Theory of Communication, C.E. Shannon et W. Weaver, The University of Illinois Press, 1949). | MR 26286 | Zbl 1154.94303

[51] Wolfgang Thomas. Automata on infinite objects. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, chapter 4. North Holland, 1990. | MR 1127189 | Zbl 0900.68316

[52] Boris A. Trahtenbrot. La synthèse des réseaux logiques dont les opérateurs sont décrits en termes de calcul des prédicats à une place (en russe). Doklady Acad. Nauk. SSSR, 118:646-649, 1958.

[53] Alan M. Turing. On computable numbers with an application to the Entscheidungsproblem. Proceedings of the London Math. Soc., 42:230-265, 1936. | JFM 62.1059.03 | MR 1577030

[54] John Von Neumann. The general and logical theory of automata. In L.A.Jeffress, editor, the Hixon Symposium (Sept. 1948, pasadena). Wiley, 1951. (reproduit dans 'Collected Works', Volume V, Pergarnon Press, 1961). | MR 45446

[55] Benjamin Weiss. Subshifts of finite type and sofic systems. Monats. Math., 77:462 474, 1973. | MR 340556 | Zbl 0285.28021