Bibliographie

Langages rationnels

[BBC93] G. Beauquier, J. Berstel, and P. Chrétienne, Éléments d'algorithmique. Masson, 1993.
[Eil72] S. Eilenberg, Automata, Languages and Machines, vol. A. New York: Academic Press, 1972.
[Eil76] S. Eilenberg, Automata, Languages and Machines, vol. B. New York: Academic Press, 1976.
[HU79] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.
[Per90] D. Perrin, Finite automata, in Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), vol. B, chapt. 1, pp. 1-57, Elsevier, 1990.
[Pin86] J.-É. Pin, Variétés de Langages Formels. Masson, 1984.
[Sak03] J. Sakarovitch, Éléments de théorie des automates. Vuibert, 2003.
[Str94] H. Straubing, Finite Automata, Formal Logic and Circuits Complexity. Progress in theoretical computer science, Birkhäuser, 1994.
[TB73] B. Trachtenbrot and Y. Barzdin, Finite Automata. North Holland, 1973.
[PP04] D. Perrin and J.-É. Pin, Infinite Words. Elsevier, 2004.

Combinatoire

[VLW92] J. H. van Lint and R. M. Wilson, A Course in Combinatorics. Cambridge University Press, 1992.

Langages algébriques

[Aut87] J.-M. Autebert, Langages algébriques. Masson, 1987.
[AB88] J.-M. Autebert and L. Boasson, Transductions Rationnelles : Application aux Langages Algébriques. Paris: Masson, 1988.
[ABB97] J.-M. Autebert, J. Berstel, and L. Boasson, Context-Free Languages and Pushdown Automata, in Handbook of formal languages, vol. 1, pp. 111-174, Springer, 1997.
[Ber79] J. Berstel, Transductions and Context-Free Languages. B.G. Teubner, 1979.
[BB90] J. Bestel and L. Boasson, Context-Free languages, in Handbook of Theoretical Computer Science (J. van Leeuwen, ed.), vol. B, chapt. 2, pp. 59-102, Elsevier, 1990.

Calculabilité et complexité

Les deux premières références sont des grands classiques incontournables. Les deux suivantes sont plus faciles d'accès. Ces deux livres sont plus limités mais ils contiennent l'essentiel.

[HU74] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1974.
[Sip97] M. Sipser, Introduction to the Theory of Computation. PWS publishing Company, 1997.
[Aut92] J.-M. Autebert, Calculabilité et Décidabilité. Masson, 1992.
[Wol91] P. Wolper, Introduction à la calculabilité. InterÉditions, 1991.
[Deh91] P. Dehornoy, Complexité et Calculabilité. Springer-Verlag, 1991.
[Deh00] P. Dehornoy, Mathématiques de l'informatique. Dunod, 2000.
[Rey04] J.-F. Rey, Calculablité, Complexité et Approximation. Vuibert, 2004.
[LP81] H. R. Lewis and C. Papadimitriou, Elements of the theory of computation. Prentice-Hall, 1981.
[GJ79] M. Garey and D. Johnson, Computers and intractability. W.H. Freeman & Co, 1979.
[Pap95] C. Papadimitriou, Computational complexity. Addison-Wesley, 1995.
[Wel88] D. Welsh, Codes and Cryptography. Clarendon Press, 1988.
[Ste90] J. Stern, Fondements mathématiques de l'informatique. McGraw-Hill, 1990.
[MR95] R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge University Press, 1995.