En matemáticas , y particularmente en la teoría de los lenguajes formales , shortlex es un ordenamiento total de secuencias finitas de objetos que pueden ordenarse totalmente. En el ordenamiento shortlex, las secuencias se ordenan principalmente por cardinalidad (longitud) con las secuencias más cortas primero, y las secuencias de la misma longitud se clasifican en orden lexicográfico . [1] La ordenación Shortlex también se llama ordenación radical , lexicográfica de longitud , militar o genealógica . [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 cadenas más largas. Por ejemplo, el orden abreviado 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 orden sobre un alfabeto finito fijo se pueden colocar en correspondencia uno a uno preservando el orden con los enteros no negativos , dando el sistema de numeración biyectiva para representar números. [3] El ordenamiento shortlex también es importante en la teoría de grupos automáticos . [4]
Referencias
- ^ Sipser, Michael (2012). Introducción a la teoría de la computación (3 ed.). Boston, MA: Aprendizaje Cengage. pag. 14 . ISBN 978-1133187790.
- ^ Bárány, Vince (2008), "Una jerarquía de palabras ω automáticas que tienen 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. Ordenamiento lexicográfico; representación n -ádica de números enteros" , Teoría de sistemas formales , Annals of Mathematics Studies, 47 , Princeton University Press, págs. 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. 56, ISBN 0-86720-244-0, MR 1161694.