Orden de Shortlex

En matemáticas , y particularmente en la teoría de lenguajes formales , el ordenamiento shortlex es un ordenamiento total para secuencias finitas de objetos que, a su vez, pueden ordenarse totalmente. En el ordenamiento shortlex, las secuencias se ordenan principalmente por cardinalidad (longitud), colocando primero las más cortas, y las secuencias de la misma longitud se ordenan lexicográficamente . ^{[ 1 ]} El ordenamiento shortlex también se denomina ordenamiento radix , lexicográfico por longitud , militar o genealógico . ^{[ 2 ]}

En el contexto de cadenas en un alfabeto totalmente ordenado, el orden shortlex es idéntico al orden lexicográfico, excepto que las cadenas más cortas preceden a las más largas. Por ejemplo, el orden shortlex del conjunto de cadenas en el alfabeto inglés (en su orden habitual) es [ ε, a, b, c, ..., z, aa, ab, ac, ..., zz, aaa, aab, aac, ..., zzz, ... ], donde ε denota la cadena vacía .

Las cadenas en este ordenamiento sobre un alfabeto finito fijo pueden colocarse en correspondencia biunívoca que preserva el orden con los números naturales , dando lugar al sistema de numeración biyectivo para representar números. ^{[ 3 ]} El ordenamiento shortlex también es importante en la teoría de grupos automáticos . ^{[ 4 ]}

Véase también

Referencias

↑ Sipser, Michael (2012). Introducción a la teoría de la computación (3.ª ed.). Boston, MA: Cengage Learning. pág . 14. ISBN 978-1133187790.
↑ Bárány, Vince (2008), "Una jerarquía de palabras ω automáticas con una teoría MSO decidible", RAIRO Theoretical Informatics and Applications , 42 (3): 417–450 , doi : 10.1051/ita:2008008 , MR 2434027 .
↑ Smullyan, R. (1961), "9. Ordenación lexicográfica; representación n -ádica de enteros" , Theory of Formal Systems , Annals of Mathematics Studies, vol. 47, Princeton University Press, pp . 34–36 .
↑ Epstein, David BA ; Cannon, James W.; Holt, Derek F.; Levy, Silvio VF; Paterson, Michael S .; Thurston, William P. (1992), Procesamiento de textos en grupos , Boston, MA: Jones and Bartlett Publishers, pág. 56, ISBN 0-86720-244-0, MR 1161694 .

[1] Sipser, Michael (2012). Introducción a la teoría de la computación (3.ª ed.). Boston, MA: Cengage Learning. pág . 14. ISBN 978-1133187790.

[2] Bárány, Vince (2008), "Una jerarquía de palabras ω automáticas con una teoría MSO decidible", RAIRO Theoretical Informatics and Applications , 42 (3): 417–450 , doi : 10.1051/ita:2008008 , MR 2434027 .

[3] Smullyan, R. (1961), "9. Ordenación lexicográfica; representación n -ádica de enteros" , Theory of Formal Systems , Annals of Mathematics Studies, vol. 47, Princeton University Press, pp . 34–36 .

[4] Epstein, David BA ; Cannon, James W.; Holt, Derek F.; Levy, Silvio VF; Paterson, Michael S .; Thurston, William P. (1992), Procesamiento de textos en grupos , Boston, MA: Jones and Bartlett Publishers, pág. 56, ISBN 0-86720-244-0, MR 1161694 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]