Secuencia de De Bruijn

En matemáticas combinatorias , una secuencia de De Bruijn de orden n sobre un alfabeto A de tamaño k es una secuencia cíclica en la que cada cadena posible de longitud n sobre A aparece exactamente una vez como subcadena (es decir, como una subsecuencia contigua ). Dicha secuencia se denota por B ( k , n ) y tiene una longitud kn ^, que también es el número de cadenas distintas de longitud n sobre A. Cada una de estas cadenas distintas, al ser tomada como subcadena de B ( k , n ) , debe comenzar en una posición diferente, ya que las subcadenas que comienzan en la misma posición no son distintas. Por lo tanto, B ( k , n ) debe tener al menos kn símbolos. Y dado que B ( k , n ) tiene exactamente kn ^{símbolos , las} secuencias de De Bruijn son óptimamente cortas con respecto a la propiedad de contener cada cadena de longitud n al menos una vez.

El número de secuencias distintas de De Bruijn B ( k , n ) es

${\displaystyle {\dfrac {\left(k!\right)^{k^{n-1}}}{k^{n}}}.}$

Para un alfabeto binario, esto es , lo que lleva a la siguiente secuencia para positivo : 1, 1, 2, 16, 2048, 67108864... ((secuencia A016031 en el OEIS )) ${\displaystyle 2^{2^{(n-1)}-n}}$${\displaystyle n}$

Las secuencias reciben su nombre del matemático neerlandés Nicolaas Govert de Bruijn , quien escribió sobre ellas en 1946. ^{[ 1 ]} Como escribió posteriormente, ^{[ 2 ]} la existencia de secuencias de De Bruijn para cada orden, junto con las propiedades mencionadas anteriormente, fue demostrada por primera vez , para el caso de alfabetos con dos elementos, por Camille Flye Sainte-Marie ( 1894 ). La generalización a alfabetos más grandes se debe a Tatyana van Aardenne-Ehrenfest y de Bruijn ( 1951 ). Los autómatas para reconocer estas secuencias se denominan autómatas de De Bruijn.

En muchas aplicaciones, A = {0,1}.

El ejemplo más antiguo conocido de una secuencia de De Bruijn proviene de la prosodia sánscrita , donde, desde la obra de Pingala , a cada posible patrón de tres sílabas, con sílabas largas y cortas, se le da un nombre, como 'y' para corta-larga-larga y 'm' para larga-larga-larga. Para recordar estos nombres, se utiliza la mnemotecnia yamātārājabhānasalagām , en la que cada patrón de tres sílabas comienza con su nombre: 'yamātā' tiene un patrón corto-largo-largo, 'mātārā' tiene un patrón largo-largo-largo, y así sucesivamente, hasta 'salagām', que tiene un patrón corto-corto-largo. Esta regla mnemotécnica, equivalente a una secuencia de De Bruijn sobre 3-tuplas binarias, es de antigüedad desconocida, pero es al menos tan antigua como el libro de Charles Philip Brown de 1869 sobre prosodia sánscrita que la menciona y la considera "un verso antiguo, escrito por Pāṇini ". ^{[ 3 ]}

En 1894, A. de Rivière planteó en un número de la revista francesa de problemas L'Intermédiaire des Mathématiciens la cuestión de la existencia de una disposición circular de ceros y unos de tamaño que contuviera todas las secuencias binarias de longitud . El problema fue resuelto (afirmativamente), junto con el número de soluciones distintas, por Camille Flye Sainte-Marie ese mismo año. ^{[ 2 ]} Esto quedó en gran medida en el olvido, y Martin (1934) demostró la existencia de tales ciclos para un tamaño de alfabeto general en lugar de 2, con un algoritmo para construirlos. Finalmente, cuando en 1944 Kees Posthumus conjeturó el número de secuencias binarias, de Bruijn demostró la conjetura en 1946, gracias a lo cual el problema se hizo muy conocido. ^{[ 2 ]}${\displaystyle 2^{n}}$${\displaystyle 2^{n}}$${\displaystyle n}$${\displaystyle 2^{2^{n-1}-n}}$${\displaystyle 2^{2^{n-1}-n}}$

Karl Popper describe de forma independiente estos objetos en su obra La lógica del descubrimiento científico (1934), llamándolos "secuencias aleatorias más cortas". ^{[ 4 ]}

• Tomando A = {0, 1}, hay dos B (2, 3) distintos: 00010111 y 11101000, uno de los cuales es el inverso o la negación del otro.
• Dos de las 16 posibles B (2, 4) en el mismo alfabeto son 0000100110101111 y 0000111101100101.
• Dos de las 2048 posibles B (2, 5) en el mismo alfabeto son 00000100011001010011101011011111 y 00000101001000111110111001101011.

Las secuencias de De Bruijn se pueden construir tomando un camino hamiltoniano de un grafo de De Bruijn n- dimensional sobre k símbolos (o equivalentemente, un ciclo euleriano de un grafo de De Bruijn ( n  -1)-dimensional). ^{[ 5 ]}

Una construcción alternativa consiste en concatenar, en orden lexicográfico , todas las palabras de Lyndon cuya longitud divide a n . ^{[ 6 ]}

Se puede utilizar una transformada inversa de Burrows-Wheeler para generar las palabras de Lyndon requeridas en orden lexicográfico. ^{[ 7 ]}

Las secuencias de De Bruijn también se pueden construir utilizando registros de desplazamiento ^{[ 8 ]} o mediante campos finitos . ^{[ 9 ]}

Objetivo: construir una secuencia B (2, 4) de Bruijn de longitud 2 ⁴ = 16 usando  el ciclo del gráfico de Bruijn tridimensional euleriano ( n − 1 = 4 − 1 = 3).

Cada arista en este grafo de De Bruijn tridimensional corresponde a una secuencia de cuatro dígitos: los tres dígitos que identifican el vértice del que parte la arista, seguidos del dígito que identifica la arista misma. Si se recorre la arista con el dígito 1 desde 000, se llega a 001, lo que indica la presencia de la subsecuencia 0001 en la secuencia de De Bruijn. Recorrer cada arista exactamente una vez implica utilizar cada una de las 16 secuencias de cuatro dígitos exactamente una vez.

Por ejemplo, supongamos que seguimos el siguiente camino euleriano a través de estos vértices:

000, 000, 001, 011, 111, 111, 110, 101, 011,

110, 100, 001, 010, 101, 010, 100, 000.

Estas son las secuencias de salida de longitud k :

0 0 0 0

_ 0 0 0 1

_ _ 0 0 1 1

Esto corresponde a la siguiente secuencia de De Bruijn:

0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1

Los ocho vértices aparecen en la secuencia de la siguiente manera:

 {0 0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1 0 {0 0 0 1} 1 1 1 0 1 1 0 0 1 0 1 0 0 {0 0 1 1} 1 1 0 1 1 0 0 1 0 1 0 0 0 {0 1 1 1} 1 0 1 1 0 0 1 0 1 0 0 0 0 {1 1 1 1} 0 1 1 0 0 1 0 1 0 0 0 0 1 {1 1 1 0} 1 1 0 0 1 0 1 0 0 0 0 1 1 {1 1 0 1} 1 0 0 1 0 1 0 0 0 0 1 1 1 {1 0 1 1} 0 0 1 0 1 0 0 0 0 1 1 1 1 {0 1 1 0} 0 1 0 1 0 0 0 0 1 1 1 1 0 {1 1 0 0} 1 0 1 0 0 0 0 1 1 1 1 0 1 {1 0 0 1} 0 1 0 0 0 0 1 1 1 1 0 1 1 {0 0 1 0} 1 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0 1} 0} 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1 ... ... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ... ... 0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 {1 ... 

...y luego volvemos al punto de partida. Cada una de las ocho secuencias de 3 dígitos (que corresponden a los ocho vértices) aparece exactamente dos veces, y cada una de las dieciséis secuencias de 4 dígitos (que corresponden a las 16 aristas) aparece exactamente una vez.

Matemáticamente, una transformada inversa de Burrows-Wheeler sobre una palabra w genera un multiconjunto de clases de equivalencia que consisten en cadenas y sus rotaciones. ^{[ 7 ]} Cada una de estas clases de equivalencia de cadenas contiene una palabra de Lyndon como elemento mínimo único, por lo que la transformada inversa de Burrows-Wheeler puede considerarse que genera un conjunto de palabras de Lyndon. Se puede demostrar que si realizamos la transformada inversa de Burrows-Wheeler sobre una palabra w que consiste en el alfabeto de tamaño k repetido k ^{n −1} veces (de modo que producirá una palabra de la misma longitud que la secuencia de De Bruijn deseada), entonces el resultado será el conjunto de todas las palabras de Lyndon cuya longitud divide a n . De ello se deduce que ordenar estas palabras de Lyndon en orden lexicográfico producirá una secuencia de De Bruijn B ( k , n ), y que esta será la primera secuencia de De Bruijn en orden lexicográfico. El siguiente método puede utilizarse para realizar la transformada inversa de Burrows-Wheeler, utilizando su permutación estándar :

1. Ordena los caracteres de la cadena w , obteniendo una nueva cadena w ′.
2. Coloca la cadena w ′ encima de la cadena w , y asigna la posición de cada letra en w ′ a su posición en w manteniendo el orden. Este proceso define la permutación estándar .
3. Escribe esta permutación en notación cíclica, colocando primero la posición más pequeña en cada ciclo y ordenando los ciclos de forma ascendente.
4. Para cada ciclo, reemplace cada número con la letra correspondiente de la cadena w ′ en esa posición.
5. Cada ciclo se ha convertido ahora en una palabra de Lyndon, y están ordenados lexicográficamente, por lo que al eliminar los paréntesis se obtiene la primera secuencia de De Bruijn.

Por ejemplo, para construir la secuencia de De Bruijn B (2,4) más pequeña de longitud 2 ⁴ = 16, repita el alfabeto (ab) 8 veces, obteniendo w = abababababababab . Ordene los caracteres en w , obteniendo w ′ = aaaaaaaabbbbbbbb . Coloque w ′ encima de w como se muestra, y asigne cada elemento de w ′ al elemento correspondiente en w dibujando una línea. Numere las columnas como se muestra para que podamos leer los ciclos de la permutación:

Comenzando desde la izquierda, los ciclos de la notación de permutación estándar son: (1) (2 3 5 9) (4 7 13 10) (6 11) (8 15 14 12) (16) . ( Permutación estándar )

Luego, reemplazando cada número por la letra correspondiente en w ′ de esa columna se obtiene: (a)(aaab)(aabb)(ab)(abbb)(b) .

Estas son todas las palabras de Lyndon cuya longitud divide a 4, en orden lexicográfico, por lo que eliminando los paréntesis se obtiene B (2,4) = aaaabaabbababbbb .

El siguiente código Python calcula una secuencia de De Bruijn, dados k y n , basándose en un algoritmo de Generación Combinatoria de Frank Ruskey . ^{[ 10 ]}

from typing import Iterable , Any def de_bruijn ( k : Iterable [ str ] | int , n : int ) -> str : """Secuencia de De Bruijn para el alfabeto k  y subsecuencias de longitud n.  """ # Dos tipos de entrada de alfabeto: un entero se expande # a una lista de enteros como el alfabeto.. if isinstance ( k , int ): alphabet = list ( map ( str , range ( k ))) else : # Mientras que cualquier tipo de lista se usa como es alphabet = k k = len ( k )a = [ 0 ] * k * n secuencia = []def db ( t , p ): if t > n : if n % p == 0 : sequence . extend ( a [ 1 : p + 1 ]) else : a [ t ] = a [ t - p ] db ( t + 1 , p ) for j in range ( a [ t - p ] + 1 , k ): a [ t ] = j db ( t + 1 , t )db ( 1 , 1 ) devuelve "" . join ( alphabet [ i ] para i en secuencia )imprimir ( de_bruijn ( 2 , 3 )) imprimir ( de_bruijn ( "abcd" , 2 ))

que imprime

00010111 aabacadbbcbdccdd 

Cabe destacar que estas secuencias se entienden como ciclos que se repiten. Por ejemplo, la primera secuencia contiene 110 y 100 de esta manera.

Los ciclos de De Bruijn son de uso general en experimentos de neurociencia y psicología que examinan el efecto del orden de los estímulos sobre los sistemas neuronales, ^{[ 11 ]} y pueden diseñarse especialmente para su uso con imágenes de resonancia magnética funcional . ^{[ 12 ]}

Los símbolos de una secuencia de De Bruijn escrita alrededor de un objeto circular (como la rueda de un robot ) pueden usarse para identificar su ángulo examinando los n símbolos consecutivos que apuntan a un punto fijo. Este problema de codificación de ángulos se conoce como el "problema del tambor giratorio". ^{[ 13 ]} Los códigos Gray pueden usarse como mecanismos de codificación de posición rotatoria similares, un método que se encuentra comúnmente en los codificadores rotatorios .

Una secuencia de De Bruijn se puede utilizar para encontrar rápidamente el índice del bit menos significativo ("1 de la derecha") o del bit más significativo ("1 de la izquierda") en una palabra mediante operaciones bit a bit y multiplicación. ^{[ 14 ]} El siguiente ejemplo utiliza una secuencia de De Bruijn para determinar el índice del bit menos significativo (equivalente a contar el número de bits '0' finales) en un entero sin signo de 32 bits :

uint8_t lowestBitIndex ( uint32_t v ) { static const uint8_t BitPositionLookup [ 32 ] = // tabla hash { 0 , 1 , 28 , 2 , 29 , 14 , 24 , 3 , 30 , 22 , 20 , 15 , 25 , 17 , 4 , 8 , 31 , 27 , 13 , 23 , 21 , 19 , 16 , 7 , 26 , 12 , 18 , 6 , 11 , 5 , 10 , 9 }; return BitPositionLookup [(( uint32_t )(( v & - v ) * 0x077CB531U )) >> 27 ]; }

La lowestBitIndex()función devuelve el índice del bit menos significativo activado en v , o cero si v no tiene bits activados. La constante 0x077CB531U en la expresión es la secuencia B (2, 5) 0000 0111 0111 1100 1011 0101 0011 0001 (espacios añadidos para mayor claridad). La operación (v & -v)pone a cero todos los bits excepto el bit menos significativo activado, lo que da como resultado un nuevo valor que es una potencia de 2. Esta potencia de 2 se multiplica (aritmética módulo 2 ³² ) por la secuencia de De Bruijn, produciendo así un producto de 32 bits en el que la secuencia de bits de los 5 MSB es única para cada potencia de 2. Los 5 MSB se desplazan a las posiciones LSB para producir un código hash en el rango [0, 31], que luego se utiliza como índice en la tabla hash BitPositionLookup. El valor de la tabla hash seleccionado es el índice del bit menos significativo establecido en v .

El siguiente ejemplo determina el índice del bit más significativo activado en un entero sin signo de 32 bits:

uint32_t keepHighestBit ( uint32_t n ) { n |= ( n >> 1 ); n |= ( n >> 2 ); n |= ( n >> 4 ); n |= ( n >> 8 ); n |= ( n >> 16 ); return n - ( n >> 1 ); }uint8_t highestBitIndex ( uint32_t v ) { static const uint8_t BitPositionLookup [ 32 ] = { // tabla hash 0 , 1 , 16 , 2 , 29 , 17 , 3 , 22 , 30 , 20 , 18 , 11 , 13 , 4 , 7 , 23 , 31 , 15 , 28 , 21 , 19 , 10 , 12 , 6 , 14 , 27 , 9 , 5 , 26 , 8 , 25 , 24 , }; return BitPositionLookup [( keepHighestBit ( v ) * 0x06EB14F9U ) >> 27 ]; }

En el ejemplo anterior, se utiliza una secuencia de De Bruijn alternativa (0x06EB14F9U), con la correspondiente reordenación de los valores del array. La elección de esta secuencia de De Bruijn en particular es arbitraria, pero los valores de la tabla hash deben ordenarse para que coincidan con la secuencia de De Bruijn elegida. La keepHighestBit()función pone a cero todos los bits excepto el bit más significativo, lo que da como resultado un valor que es una potencia de 2, el cual se procesa como en el ejemplo anterior.

Una secuencia de De Bruijn se puede utilizar para acortar un ataque de fuerza bruta en una cerradura de código tipo PIN que no tiene tecla "Enter" y acepta los últimos n dígitos introducidos. Por ejemplo, una cerradura digital con un código de 4 dígitos (cada dígito con 10 posibilidades, del 0 al 9) tendría B (10, 4) soluciones, con una longitud de10 000. Por lo tanto, solo como máximo10 000 + 3 =Se necesitan 10 003 pulsaciones (ya que las soluciones son cíclicas) para abrir la cerradura, mientras que probar todos los códigos por separado requeriría 4 ×10 000 =40 000 prensas.

Una secuencia de De Bruijn n-aria f-múltiple es una extensión de la noción de secuencia de De Bruijn n -aria, de tal manera que la secuencia de longitud contiene cada subsecuencia posible de longitud n exactamente f veces. Por ejemplo, para las secuencias cíclicas 11100010 y 11101000 son secuencias de De Bruijn binarias dos veces. El número de secuencias de De Bruijn dos veces, para es , los otros números conocidos ^{[ 16 ]} son ​​, , y . ${\displaystyle fk^{n}}$${\displaystyle n=2}$${\displaystyle N_{n}}$${\displaystyle n=1}$${\displaystyle N_{1}=2}$${\displaystyle N_{2}=5}$${\displaystyle N_{3}=72}$${\displaystyle N_{4}=43768}$

Un toro de De Bruijn es una matriz toroidal con la propiedad de que cada matriz k -aria de m por n aparece exactamente una vez.

Dicho patrón puede utilizarse para la codificación posicional bidimensional de forma análoga a la descrita anteriormente para la codificación rotatoria. La posición se determina examinando la matriz de m × n adyacente al sensor y calculando su posición en el toro de De Bruijn.

Calcular la posición de una tupla o matriz única en una secuencia o toro de De Bruijn se conoce como el problema de decodificación de De Bruijn . Existen algoritmos de decodificación eficientes para secuencias${\displaystyle \color {Blue}O(n\log n)}$ especiales construidas recursivamente ^{[ 17 ]} y se extienden al caso bidimensional ^{[ 18 ]} . La decodificación de De Bruijn es de interés, por ejemplo, en casos donde se utilizan secuencias o toros grandes para la codificación posicional.

• Número normal
• Registro de desplazamiento con retroalimentación lineal
• secuencia n
• MEJOR teorema
• Superpermutación

• van Aardenne-Ehrenfest, Tanja ; de Bruijn, Nicolaas Govert (1951). «Circuitos y árboles en grafos lineales orientados» (PDF) . Simón Stevin . 28 : 203-217 . SEÑOR  0047311 .
• Aguirre, GK; Mattar, MG; Magis-Weinberg, L. (2011). " Ciclos de De Bruijn para la decodificación neuronal" . NeuroImage . 56 (3): 1293– 1300. doi : 10.1016/j.neuroimage.2011.02.005 . PMC  3104402. PMID  21315160. Archivado del original el 26 de enero de 2016. Consultado el 4 de junio de 2015 .
• Anderson, Sean Eron (1997–2009). "Trucos de manipulación de bits" . Universidad de Stanford . Recuperado el 12 de febrero de 2009 .
• Berstel, Jean ; Perrin, Dominique (2007). "Los orígenes de la combinatoria en palabras" (PDF) . European Journal of Combinatorics . 28 (3): 996–1022 . doi : 10.1016/j.ejc.2005.07.019 . MR  2300777 .
• Brown, CP (1869). Explicación de la prosodia y los símbolos numéricos sánscritos . pág. 28.
• de Bruijn, Nicolaas Govert (1946). «Un problema combinatorio» (PDF) . Proc. Koninklijke Nederlandse Akademie V. Wetenschappen . 49 : 758–764 . SEÑOR  0018142 , Indagationes Mathematicae 8 : 461–467{{cite journal}}: CS1 maint: postscript (link)
• de Bruijn, Nicolaas Govert (1975). Reconocimiento de prioridad a C. Flye Sainte-Marie sobre el conteo de arreglos circulares de 2 ⁿ ceros y unos que muestran cada palabra de n letras exactamente una vez (PDF) . Informe TH 75-WSK-06. Universidad Tecnológica de Eindhoven.
• Busch, Philip (2009). "Cómo calcular ceros finales" . Archivado del original el 29 de enero de 2015. Recuperado el 29 de enero de 2015 .
• Flye Sainte-Marie, Camille (1894). "Solución a la pregunta nº 48". L'Intermédiaire des Mathématiciens . 1 : 107-110 .
• Goresky, Mark ; Klapper, Andrew (2012). "8.2.5 Generación de secuencias de De Bruijn mediante registros de desplazamiento". Secuencias algebraicas de registros de desplazamiento . Cambridge University Press . págs.  174–175 . ISBN 978-1-10701499-2.
• Hall, Rachel W. (2008). "Matemáticas para poetas y bateristas" (PDF) . Math Horizons . 15 (3): 10– 11. doi : 10.1080/10724117.2008.11974752 . S2CID  3637061. Archivado del original (PDF) el 12 de febrero de 2012. Recuperado el 22 de octubre de 2008 .
• Higgins, Peter (noviembre de 2012). "Transformaciones de Burrows-Wheeler y palabras de De Bruijn" (PDF) . Recuperado el 11 de febrero de 2017 .
• Hurlbert, Glenn; Isaak, Garth (1993). "Sobre el problema del toro de De Bruijn" . Journal of Combinatorial Theory . Serie A. 64 (1): 50– 62. doi : 10.1016/0097-3165(93)90087-O . MR  1239511 .
• Kak, Subhash (2000). "Yamātārājabhānasalagāṃ un interesante sutra combinatorio" (PDF) . Indian Journal of History of Science . 35 (2): 123– 127. Archivado del original (PDF) el 29 de octubre de 2014.
• Klein, Andreas (2013). Cifrados de flujo . Springer. pág. 59. ISBN 978-1-44715079-4.
• Knuth, Donald Ervin (2006). El arte de la programación informática, Fascículo 4: Generación de todos los árboles – Historia de la generación combinatoria . Addison–Wesley . p. 50. ISBN 978-0-321-33570-8.
• Fredricksen, Harold; Maiorana, James (1978). "Collares de cuentas en k colores y secuencias de De Bruijn k -arias" . Matemáticas Discretas . 23 (3): 207– 210. doi : 10.1016/0012-365X(78)90002-X . MR  0523071 .
• Martin, Monroe H. (1934). "Un problema en arreglos" (PDF) . Boletín de la Sociedad Matemática Americana . 40 (12): 859– 864. doi : 10.1090/S0002-9904-1934-05988-3 . MR  1562989 .
• Osipov, Vladimir (2016). "Análisis de ondículas en secuencias simbólicas y secuencias de De Bruijn dobles". Journal of Statistical Physics . 164 (1): 142– 165. arXiv : 1601.02097 . Bibcode : 2016JSP...164..142O . doi : 10.1007/s10955-016-1537-5 . ISSN  1572-9613 . S2CID  16535836 .
• Popper, Karl (2002) [1934]. La lógica del descubrimiento científico . Routledge. pág. 294. ISBN 978-0-415-27843-0.
• Ralston, Anthony (1982). " Secuencias de De Bruijn: un ejemplo modelo de la interacción entre las matemáticas discretas y la informática". Mathematics Magazine . 55 (3): 131– 143. doi : 10.2307/2690079 . JSTOR  2690079. MR  0653429 .
• Stein, Sherman K. (1963). "Yamátárájabhánasalagám". El universo creado por el hombre: una introducción al espíritu de las matemáticas . págs.  110–118 .Reimpreso en Wardhaugh, Benjamin, ed. (2012), A Wealth of Numbers: An Anthology of 500 Years of Popular Mathematics Writing , Princeton University Press , pp. 139–144.
• Tuliani, Jonathan (2001). "Secuencias de De Bruijn con algoritmos de decodificación eficientes". Matemáticas Discretas . 226 ( 1– 3): 313– 336. doi : 10.1016/S0012-365X(00)00117-5 . MR  1802599 .
• van Lint, JH ; Wilson, Richard Michael (2001). Un curso de combinatoria . Cambridge University Press . pág. 71. ISBN 978-0-52100601-9.

• Weisstein, Eric W. "Secuencia de Bruijn" . MundoMatemático .
• Secuencia OEIS A166315 (secuencias binarias de Bruijn lexicográficamente más pequeñas)
• Secuencia de De Bruijn Archivado el 11 de abril de 2011 en la Wayback Machine.
• generador CGI
• Generador de applets
• Generador y decodificador de Javascript . Implementación del algoritmo de J. Tuliani.
• Cerradura de código de puerta
• Matrices mínimas que contienen todas las combinaciones de submatrices de símbolos: secuencias de De Bruijn y toros.
• http://debruijnsequence.org tiene muchos tipos de secuencias de De Bruijn.