Utilisateur:Vers75/Codes
Codes à trois mots
modifierÉnoncés
modifierUn premier résultat — plutôt facile — concerne les codes à deux mots :
Théorème — Un ensemble formé de deux mots non vides est un code si et seulement si et ne sont pas puissances d'un même mot.
L'étude des codes à trois mots, entreprise déjà dans les années 1980, est plus compliquée[1].
Des cas particuliers ont été étudiés : si les mots sont primitifs, ou plus généralement sans bord.
Un exemple d'énoncé sans condition sur la nature des mots, seulement sur leur longueur, est le suivant :
Théorème[1] — Un ensemble formé de trois mots non vides, avec est un code si et seulement si les conditions suivantes sont satisfaites :
- n'est pas un produit de mots et .
- Le mot ne commute pas avec , et de plus .
Exemples
modifier1.- L'ensemble {a, aaab, baaaa} n'est pas un code car (aaab)a^4=a^3(baaaa)
2.- L'ensemble {ab, ba, aba} n'est pas un code car (ab)(aba)=(ab)(ba)
3.- L'ensemble {aba, bab, abab} n'est pas un code car (aba)(bab)(abab) = (abab)(aba)(bab)
4.- L'ensemble {aba, bab, ababa} n'est pas un code car (aba)(bab)(ababa) = (ababa)(bab)(aba)
Notes et références
modifier- Cao Chunhua, Lu Qing et Yang Di, « A first step in characterizing three-element codes », Acta Informatica, vol. 55, no 5, , p. 445–457 (ISSN 0001-5903, DOI 10.1007/s00236-017-0309-2).
Bibliographie
modifier- Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata, Encyclopedia on Mathematics and Its Applications, vol. 129. Cambridge University Press, Cambridge (2009)
- Budkina, L.G., Markov, A.A.: On F-semigroups with three generators. Math. Notes 14, 711–716 (1973)
- Derencourt, D.: A three-word code which is not prefix–suffix composed. Theor. Comput. Sci. 163, 145–160 (1996)
- Karhumäki, J.: On three-element codes. Theor. Comput. Sci. 40, 3–11 (1985)
- Karhumäki, J.: A property of three-element codes. Theor. Comput. Sci. 41, 215–222 (1985)
- Karhumäki, J., Petre, I.: Conway’s problem for three-word sets. Theor. Comput. Sci. 289, 705–725 (2002)
- Li, Z.Z., Tsai, Y.S.: Three-element codes with one d-primitive word. Acta Inform. 41, 171–180 (2004)
- Li, Z.Z., Tsai, Y.S., Yih, G.C.: Characterizations on codes with three elements. Soochow J. Math. 30,177–196 (2004)
- Spehner, J.-C.: Quelques problèmes d’extension, de conjugaison et de présentation des sous-monoïdes d’un monoïde libre, Thèse de Doctorat d’État, Université de Paris VII (1976)
- Spehner, J.-C.: Les présentations des sous-monoïdes de rang 3 d’un monoïde libre, Lecture Notes in Mathematics, vol. 855, Semigroups (Proceedings of Conference Mathematical Sciences Research Institute, Oberwolfach, 1978), pp. 116–155. Springer, Berlin (1981)
- Spehner, J.-C.: Les présentations des sous-monoïdes de rang 3 d’un monoïde libre. une correction, Publications Mathématiques 31, Université de Haute Alsace (1985)
Articles liés
modifierIl y a une grande variété de pages, difficiles à grouper
- Code (information)
- Chiffrement
- Cryptosystème
- Théorie des codes
- Codage
- Codage de l'information
- Codage des caractères
- Compression de données
- Cryptage
- Transcodage
- Turbo code
- Théorème du codage de source
- Méthode de décodage
- Identité de MacWilliams
- Inégalité de Kraft
- Code de Goppa
- Canal binaire symétrique
- Canal discret
- Codage différentiel
- Codage entropique
- Code à longueur variable
- Code comma-free
- Code préfixe
- Code universel
- Codage d'Even-Rodeh
- Codage de Fibonacci
- Codage gamma
- Code génétique
- Codage de Golomb
- Codage de Huffman
- Context-adaptive variable-length coding
- Codage omega
- Codage de Rice
- Code exponentiel-Golomb
- Codage de Shannon-Fano
- Codage Manchester
- Codage NRZ
- Codage Miller
- Code Baudot