Orden lexicográfico

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En matemáticas, el orden lexicográfico o lexicográfico (también conocido como orden léxico, u orden de diccionario) es una generalización del orden alfabético de los diccionarios a secuencias de símbolos ordenados o, más generalmente, de elementos de un conjunto totalmente ordenado.

Hay varias variantes y generalizaciones del ordenamiento lexicográfico. Una variante se aplica a secuencias de diferentes longitudes comparando las longitudes de las secuencias antes de considerar sus elementos.

Otra variante, muy utilizada en combinatoria, ordena subconjuntos de un conjunto finito dado asignando un orden total al conjunto finito y convirtiendo los subconjuntos en secuencias crecientes, a las que se les aplica el orden lexicográfico.

Una generalización define un orden en un producto cartesiano de conjuntos parcialmente ordenados; este pedido es un pedido total si y solo si todos los factores del producto cartesiano están totalmente ordenados.

Motivación y definición

Las palabras en un léxico (el conjunto de palabras utilizadas en algún idioma) tienen un orden convencional, utilizado en diccionarios y enciclopedias, que depende del orden subyacente del alfabeto de símbolos utilizados para construir las palabras. El orden lexicográfico es una forma de formalizar el orden de las palabras dado el orden de los símbolos subyacentes.

La noción formal comienza con un conjunto finito A, a menudo llamado alfabeto, que está totalmente ordenado. Es decir, para cualesquiera dos símbolos a y b en A que no sean el mismo símbolo, a < b o b < a.

Las palabras de A son las secuencias finitas de símbolos de A, incluidas las palabras de longitud 1 que contienen un solo símbolo, las palabras de longitud 2 con 2 símbolos, etc., incluso la secuencia vacía $varepsilon$ sin ningún símbolo. El orden lexicográfico sobre el conjunto de todas estas palabras finitas ordena las palabras de la siguiente manera:

Dadas dos palabras diferentes de la misma longitud, digamos a = a ₁a ₂... a _k y b = b ₁b ₂... b _k, el orden de las dos palabras depende del orden alfabético de los símbolos en el primer lugar i donde las dos palabras difieren (contando desde el comienzo de las palabras): a < b si y solo si a _i < b _i en el orden subyacente del alfabeto A.
Si dos palabras tienen diferentes longitudes, el orden lexicográfico habitual rellena la más corta con "espacios en blanco" (un símbolo especial que se trata como más pequeño que cada elemento de A) al final hasta que las palabras tengan la misma longitud, y luego las palabras son en comparación con el caso anterior.

Sin embargo, en combinatoria, se usa con frecuencia otra convención para el segundo caso, según la cual una secuencia más corta es siempre más pequeña que una secuencia más larga. Esta variante del orden lexicográfico a veces se denomina orden shortlex.

En orden lexicográfico, la palabra "Thomas" aparece antes de "Thompson" porque primero difieren en la quinta letra ('a' y 'p'), y la letra 'a' viene antes de la letra 'p' en el alfabeto. Debido a que es la primera diferencia, en este caso la quinta letra es la "diferencia más significativa" para el orden alfabético.

Una propiedad importante del orden lexicográfico es que para cada n, el conjunto de palabras de longitud n está bien ordenado por el orden lexicográfico (siempre que el alfabeto sea finito); es decir, cada secuencia decreciente de palabras de longitud n es finita (o de manera equivalente, cada subconjunto no vacío tiene un elemento mínimo). No es cierto que el conjunto de todas las palabras finitas esté bien ordenado; por ejemplo, el conjunto infinito de palabras {b, ab, aab, aaab,...} no tiene un elemento lexicográficamente más antiguo.

Sistemas numéricos y fechas.

El orden lexicográfico se usa no solo en los diccionarios, sino también comúnmente para números y fechas.

Uno de los inconvenientes del sistema de numeración romana es que no siempre es inmediatamente obvio cuál de los dos números es el más pequeño. Por otro lado, con la notación posicional del sistema numérico hindú-árabe, comparar números es fácil, porque el orden natural de los enteros no negativos es el mismo que la variante shortlex del orden lexicográfico. De hecho, con la notación posicional, un número entero no negativo se representa mediante una secuencia de dígitos numéricos, y un número entero es mayor que otro si tiene más dígitos (ignorando los ceros iniciales) o si el número de dígitos es el mismo y el primero (más significativo) el dígito que difiere es mayor.

Para los números reales escritos en notación decimal, se usa una variante ligeramente diferente del orden lexicográfico: las partes a la izquierda del punto decimal se comparan como antes; si son iguales, las partes a la derecha del punto decimal se comparan con el orden lexicográfico. El relleno 'en blanco' en este contexto es un dígito "0" final.

Cuando también se consideran números negativos, se debe invertir el orden para comparar números negativos. Esto no suele ser un problema para los humanos, pero puede serlo para las computadoras (probar el letrero lleva algún tiempo). Esta es una de las razones para adoptar la representación en complemento a dos para representar enteros con signo en las computadoras.

Otro ejemplo de un uso no relacionado con el diccionario de la ordenación lexicográfica aparece en la norma ISO 8601 para fechas, que expresa una fecha como AAAA-MM-DD. Este esquema de formato tiene la ventaja de que el orden lexicográfico en secuencias de caracteres que representan fechas coincide con el orden cronológico: una fecha CE anterior es más pequeña en el orden lexicográfico que una fecha posterior hasta el año 9999. Esta ordenación de fechas hace que la clasificación computarizada de fechas más fácil al evitar la necesidad de un algoritmo de clasificación separado.

Monoide de palabras

El monoide de palabras sobre un alfabeto A es el monoide libre sobre A. Es decir, los elementos del monoide son las secuencias finitas (palabras) de elementos de A (incluida la secuencia vacía, de longitud 0), y la operación (multiplicación) es la concatenación de palabras. Una palabra u es un prefijo (o 'truncamiento') de otra palabra v si existe una palabra w tal que v = uw. Según esta definición, la palabra vacía ( $varepsilon$ ) es un prefijo de toda palabra, y toda palabra es un prefijo de sí misma (con w ${ estilo de visualización = varepsilon}$ ); se debe tener cuidado si estos casos han de ser excluidos.

Con esta terminología, la definición anterior del orden lexicográfico se vuelve más concisa: dado un conjunto A parcial o totalmente ordenado, y dos palabras a y b sobre A tales que b no está vacía, entonces uno tiene a < b bajo el orden lexicográfico, si se cumple al menos una de las siguientes condiciones:

a es un prefijo de b
existen palabras u, v, w (posiblemente vacías) y elementos x e y de A tales que

x < ya = uxvb = uw

Observe que, debido a la condición de prefijo en esta definición, ¿ ${displaystyle varepsilon <b,,{text{ para todos }}bneq varepsilon,}$ dónde $varepsilon$ está la palabra vacía?

Si ${ estilo de visualización , <,}$ es un orden total, $A,$ también lo es el orden lexicográfico de las palabras de $UNA.$ Sin embargo, en general, este no es un orden correcto, incluso si el alfabeto $A$ está bien ordenado. Por ejemplo, si A = { a, b }, el idioma { a b | n ≥ 0, b > ε } no tiene elemento menor en el orden lexicográfico:... < aab < ab < b.

Dado que muchas aplicaciones requieren órdenes de pozos, a menudo se usa una variante de las órdenes lexicográficas. Este buen orden, a veces llamado shortlex o orden cuasi-lexicográfico, consiste en considerar primero las longitudes de las palabras (si longitud(a) <longitud(b), entonces $a<b$ ), y, si las longitudes son iguales, usar el orden lexicográfico. Si la orden en A es buena, lo mismo es cierto para la orden shortlex.

Productos cartesianos

El orden lexicográfico define un orden sobre un producto cartesiano de conjuntos ordenados, que es un orden total cuando todos estos conjuntos están totalmente ordenados. Un elemento de un producto cartesiano ${displaystyle E_{1}timescdotstimes E_{n}}$ es una secuencia cuyo $i$ elemento pertenece a $E_{yo}$ para cada $i.$ Como evaluar el orden lexicográfico de secuencias compara solo elementos que tienen el mismo rango en las secuencias, el orden lexicográfico se extiende a productos cartesianos de conjuntos ordenados.

Específicamente, dados dos conjuntos parcialmente ordenados $A$ y $B,$ elEl orden lexicográfico sobre el producto cartesiano $Aveces B$ se define como

{displaystyle (a,b)leq left(a^{prime },b^{prime }right){text{ si y solo si}}a<a^{prime }{text { o }}left(a=a^{prime }{text{ y }}bleq b^{prime }right),}

El resultado es un pedido parcial. Si $A$ y $B$ están totalmente ordenados, entonces el resultado es también un orden total. El orden lexicográfico de dos conjuntos totalmente ordenados es, por tanto, una extensión lineal de su orden de productos.

Se puede definir de manera similar el orden lexicográfico sobre el producto cartesiano de una familia infinita de conjuntos ordenados, si la familia está indexada por los números enteros no negativos, o más generalmente por un conjunto bien ordenado. Este orden lexicográfico generalizado es un orden total si cada conjunto de factores está totalmente ordenado.

A diferencia del caso finito, un producto infinito de buenos órdenes no está necesariamente bien ordenado por el orden lexicográfico. Por ejemplo, el conjunto de secuencias binarias numerables infinitas (por definición, el conjunto de funciones desde enteros no negativos hasta ${ estilo de visualización {0,1 },}$ el también conocido como espacio de Cantor ${displaystyle {0,1}^{omega }}$ ) no está bien ordenado; el subconjunto de secuencias que tienen precisamente uno $1$ (es decir, { 100000..., 010000..., 001000...,... }) no tiene un elemento mínimo bajo el orden lexicográfico inducido por ${ estilo de visualización 0 <1,}$ porque 100000... > 010000... > 001000... >... es una cadena descendente infinita. Del mismo modo, el producto lexicográfico infinito tampoco es noetheriano porque 011111... < 101111... < 110111... <...es una cadena ascendente infinita.

Funciones sobre un conjunto bien ordenado

Las funciones de un conjunto bien ordenado $X$ a un conjunto totalmente ordenado $Y$ pueden identificarse con secuencias indexadas por $X$ de elementos de $y$ Pueden así ordenarse por el orden lexicográfico, y para dos de tales funciones $F$ y ${ estilo de visualización g,}$ el orden lexicográfico está determinado por sus valores para el más pequeño $X$ tal que ${ estilo de visualización f (x) neq g (x).}$

Si $Y$ también está bien ordenado y $X$ es finito, entonces el orden resultante es un buen orden. Como se muestra arriba, si $X$ es infinito, este no es el caso.

Subconjuntos finitos

En combinatoria, a menudo hay que enumerar y, por lo tanto, ordenar los subconjuntos finitos de un conjunto dado $S.$ . Para esto, generalmente se elige un orden en $S.$ Luego, clasificar un subconjunto de $S$ es equivalente a convertirlo en una secuencia creciente. El orden lexicográfico sobre las secuencias resultantes induce así un orden sobre los subconjuntos, que también se denomina orden lexicográfico.

En este contexto, generalmente se prefiere ordenar primero los subconjuntos por cardinalidad, como en el orden shortlex. Por lo tanto, a continuación, consideraremos solo órdenes sobre subconjuntos de cardinal fijo.

Por ejemplo, usando el orden natural de los números enteros, el ordenamiento lexicográfico en los subconjuntos de tres elementos de ${displaystyle S={1,2,3,4,5,6}}$ es123 < 124 < 125 < 126 < 134 < 135 < 136 < 145 < 146 < 156 <234 < 235 < 236 < 245 < 246 < 256 < 345 < 346 < 356 < 456.

Para ordenar subconjuntos finitos de una cardinalidad dada de los números naturales, el orden colexicográfico (ver más abajo) suele ser más conveniente, porque todos los segmentos iniciales son finitos y, por lo tanto, el orden colexicográfico define un isomorfismo de orden entre los números naturales y el conjunto de conjuntos. de $norte$ números naturales. Este no es el caso del orden lexicográfico, ya que, con el orden lexicográfico, tenemos, por ejemplo, ${ estilo de visualización 12n <134}$ para cada ${ estilo de visualización n> 2.}$

Órdenes de grupo de Z^n

Sea $mathbb{Z} ^{n}$ el grupo abeliano libre de rango ${ estilo de visualización n,}$ cuyos elementos son sucesiones de $norte$ números enteros, y la operación es la suma. Una orden de grupo $mathbb{Z} ^{n}$ es una orden total, que es compatible con la suma, es decir

{displaystyle a<bquad {text{ si y solo si}}quad a+c<b+c.}

El orden lexicográfico es un orden de grupo en ${ estilo de visualización mathbb {Z} ^ {n}.}$

El orden lexicográfico también se puede utilizar para caracterizar todos los órdenes de grupo en ${ estilo de visualización mathbb {Z} ^ {n}.}$ De hecho, $norte$ las formas lineales con coeficientes reales definen un mapa desde $mathbb{Z} ^{n}$ el ${ estilo de visualización mathbb {R} ^ {n},}$ cual es inyectivo si las formas son linealmente independientes (también puede ser inyectivo si las formas son dependientes, ver más abajo). El orden lexicográfico en la imagen de este mapa induce un orden de grupo sobre ${ estilo de visualización mathbb {Z} ^ {n}.}$ el teorema de Robbiano de que todo orden de grupo puede obtenerse de esta manera.

Más precisamente, dado un orden de grupo en ${ estilo de visualización mathbb {Z} ^ {n},}$ existen formas enteras ${displaystyle sleqn}$ y $s$ lineales con coeficientes reales, de tal forma que el mapa inducido $varphi$ de $mathbb{Z} ^{n}$ hacia ${ estilo de visualización mathbb {R} ^ {s}}$ tiene las siguientes propiedades;

$varphi$ es inyectivo;
el isomorfismo resultante de $mathbb{Z} ^{n}$ a la imagen de $varphi$ es un isomorfismo de orden cuando la imagen está equipada con el orden lexicográfico en ${ estilo de visualización mathbb {R} ^ {s}.}$

Orden colexicográfico

El orden colexicográfico o colex es una variante del orden lexicográfico que se obtiene leyendo secuencias finitas de derecha a izquierda en lugar de leerlas de izquierda a derecha. Más precisamente, mientras que el orden lexicográfico entre dos secuencias está definido pora ₁a ₂... a _k < b ₁b ₂... b _ksi a _i < b _i para la primera i donde a _i y b _i difieren,

el orden colexicográfico está definido pora ₁a ₂... a _k < b ₁b ₂... b _ksi a _i < b _i para la última i donde a _i y b _i difieren

En general, la diferencia entre el orden colexicográfico y el orden lexicográfico no es muy significativa. Sin embargo, cuando se consideran secuencias crecientes, normalmente para codificar subconjuntos, los dos órdenes difieren significativamente.

Por ejemplo, para ordenar las secuencias crecientes (o los conjuntos) de dos enteros naturales, el orden lexicográfico comienza por12 < 13 < 14 < 15 <... < 23 < 24 < 25 <... < 34 < 35 <... < 45 <...,

y el orden colexicográfico comienza por12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 <....

La propiedad principal del orden colexicográfico para secuencias crecientes de una longitud dada es que cada segmento inicial es finito. En otras palabras, el orden colexicográfico para secuencias crecientes de una determinada longitud induce un isomorfismo de orden con los números naturales, y permite enumerar estas secuencias. Esto se usa con frecuencia en combinatoria, por ejemplo, en la demostración del teorema de Kruskal-Katona.

Monomios

Al considerar polinomios, el orden de los términos en general no importa, ya que la suma es conmutativa. Sin embargo, algunos algoritmos, como la división larga de polinomios, requieren que los términos estén en un orden específico. Muchos de los principales algoritmos para polinomios multivariantes están relacionados con las bases de Gröbner, concepto que requiere la elección de un orden monomio, es decir un orden total, que sea compatible con la estructura monoide de los monomios. Aquí "compatible" significa que ${displaystyle a<b{text{ implica }}ac<bc,}$ si la operación monoide se denota multiplicativamente. Esta compatibilidad implica que el producto de un polinomio por un monomio no cambia el orden de los términos. Para las bases de Gröbner, se debe cumplir una condición adicional, a saber, que todo monomio no constante sea mayor que el monomio 1. Sin embargo, esta condición no es necesaria para otros algoritmos relacionados, como los algoritmos para el cálculo del cono tangente.

Como las bases de Gröbner se definen para polinomios en un número fijo de variables, es común identificar monomios (por ejemplo $x_{1}x_{2}^{3}x_{4}x_{5}^{2}$ ) con sus vectores exponentes (aquí [1, 3, 0, 1, 2]). Si n es el número de variables, cada orden monomio es, por lo tanto, la restricción a ${ estilo de visualización mathbb {N} ^ {n}}$ de un orden monomio de $mathbb{Z} ^{n}$ (ver arriba § Órdenes de grupo de ${ estilo de visualización mathbb {Z} ^ {n},}$ para una clasificación).

Uno de estos órdenes admisibles es el orden lexicográfico. Es, históricamente, el primero que se ha utilizado para definir las bases de Gröbner, y en ocasiones se denomina orden lexicográfico puro para distinguirlo de otros órdenes que también están relacionados con un orden lexicográfico.

Otra consiste en comparar primero los grados totales, y luego resolver los conflictos utilizando el orden lexicográfico. Este orden no se usa mucho, ya que el orden lexicográfico o el orden lexicográfico de grado inverso tienen generalmente mejores propiedades.

El orden lexicográfico inverso de grados consiste también en comparar primero los grados totales y, en caso de igualdad de los grados totales, utilizar el orden inverso al colexicográfico. Es decir, dados dos vectores exponentes, uno tiene

{displaystyle [a_{1},ldots,a_{n}]<[b_{1},ldots,b_{n}]}

si alguno

{displaystyle a_{1}+cdots +a_{n}<b_{1}+cdots +b_{n},}

{displaystyle a_{1}+cdots +a_{n}=b_{1}+cdots +b_{n}quad {text{ y }}quad a_{i}>b_{i}{ text{ para el mayor }}i{text{ para el cual }}a_{i}neq b_{i}.}

Para esta ordenación, los monomios de grado uno tienen el mismo orden que los correspondientes indeterminados (no sería así si se utilizara el orden lexicográfico inverso). Para comparar monomios en dos variables del mismo grado total, este orden es el mismo que el orden lexicográfico. Este no es el caso con más variables. Por ejemplo, para vectores exponentes de monomios de grado dos en tres variables, se tiene para el orden lexicográfico inverso de grado:

{ estilo de visualización [0,0,2] <[0,1,1] <[1,0,1] <[0,2,0] <[1,1,0] <[2,0,0] }

Para el orden lexicográfico, se ordenan los mismos vectores exponenciales que

{ estilo de visualización [0,0,2] <[0,1,1] <[0,2,0] <[1,0,1] <[1,1,0] <[2,0,0].}

Una propiedad útil del orden lexicográfico de grado inverso es que un polinomio homogéneo es un múltiplo del menos indeterminado si y solo si su monomio principal (su monomio mayor) es un múltiplo de este menos indeterminado.

Contenido relacionado

Más resultados...