Les débuts de la théorie des automates
Séminaire de Philosophie et Mathématiques, no. 1 (1993), pp. 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},
     pages = {1--17},
     publisher = {IREM Paris-Nord},
     number = {1},
     year = {1993},
     language = {fr},
     url = {http://www.numdam.org/item/SPHM_1993___1_A1_0/}
}
TY  - JOUR
AU  - Perrin, Dominique
TI  - Les débuts de la théorie des automates
JO  - Séminaire de Philosophie et Mathématiques
PY  - 1993
SP  - 1
EP  - 17
IS  - 1
PB  - IREM Paris-Nord
UR  - http://www.numdam.org/item/SPHM_1993___1_A1_0/
LA  - fr
ID  - SPHM_1993___1_A1_0
ER  - 
%0 Journal Article
%A Perrin, Dominique
%T Les débuts de la théorie des automates
%J Séminaire de Philosophie et Mathématiques
%D 1993
%P 1-17
%N 1
%I IREM Paris-Nord
%U http://www.numdam.org/item/SPHM_1993___1_A1_0/
%G fr
%F 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 | Zbl

[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 | Zbl

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

[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 | Zbl

[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

[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

[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 | Zbl

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

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

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

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

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

[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 | Zbl

[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 | Zbl

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

[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

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

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

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

[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 | Zbl

[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

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

[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

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

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

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

[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

[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

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

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

[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 | Zbl

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

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | Zbl

[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 | MR

[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

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