En matemáticas , y particularmente en la teoría de los lenguajes formales , shortlex es un ordenamiento total de secuencias finitas de objetos que a su vez pueden ordenarse totalmente. En el ordenamiento shortlex, las secuencias se clasifican 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] El ordenamiento Shortlex también se denomina ordenamiento de base , lexicográfico de 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 orden sobre un alfabeto finito fijo se pueden colocar en una correspondencia uno a uno que preserve el orden con los números naturales , dando el 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]