Errata de la seconde édition
Merci à Aghilas Boussaa et Quentin Gougeon.
Pour chaque erreur est indiqué le numéro de la page et le numéro de
ligne. Les lignes sont comptées à partir du bas de la page quand le nombre
est négatif. Toutes les lignes y compris celles des formules et des titres
sont prises en compte.
Deuxième chapitre : langages algébriques
- p. 35 l. -19 : changer t′a ≼△ 0−1t ou t′′a ≼△ 1−1t en t′a ≼△ 0−1t et t′′a ≼△ 1−1t
- p. 88 l. -14 : changer propre en réduite
- p. 95 l. 13 : supprimer que
- p. 108 l. -6 : supprimer que
Troisième chapitre : calculabilité
- p. 151 l. 11 : remplacer le point . en fin de phrase
par un point d'interrogation ?
- p. 162 l. 12 : changer symbole $ en symboles $
- p. 162 l. -3 : changer suffixe propre en préfixe propre
- p. 163 l. 11 : changer une grammaires en
une grammaire
- p. 168 l. -2 : changer m ≥ n ≥ 1 en
m ≥ k ≥ 1
- p. 175 figure 3.12 : échanger les étiquettes des deux
transitions entre c et c
- p. 178 l. -8 : changer donc en en effet
- p. 181 l. 4 : changer qui n'est récursive en qui
n'est pas récursive
Quatrième chapitre : complexité
- p. 220 l. -8 : changer t est impaire en t
est impair
- p. 223 l. -8 : changer polynomiale en
logarithmique
- p. 232 l. 19 : changer que en tels que
- p. 249 l. -15 : changer supposns en supposons
- p. 249 l. -9 : changer espace loglog n si un mot d'entrée
en espace loglog n qui détermine si un mot d'entrée