Límites inferiores, y enumeración exacta en casos particulares, para la probabilidad de existencia de un ciclo universal o una palabra universal para un conjunto de palabras
Autores: Chen, Herman Z. Q.; Kitaev, Sergey; Sun, Brian Y.
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Límites inferiores, y enumeración exacta en casos particulares, para la probabilidad de existencia de un ciclo universal o una palabra universal para un conjunto de palabras
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Ciclo universal
U-ciclo
Secuencias de De Bruijn
U-palabra
Probabilidad
Existencia
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 34
Citaciones: Sin citaciones
Un ciclo universal, o u-ciclo, para un conjunto dado de palabras es una palabra circular que contiene cada palabra del conjunto exactamente una vez como una subpalabra contigua. Las celebradas secuencias de de Bruijn son un caso particular de tal u-ciclo, donde un conjunto en cuestión es el conjunto de todas las palabras de longitud sobre un alfabeto de letras. Una palabra universal, o u-palabra, es una versión lineal, es decir, no circular, de la noción de un u-ciclo, y se define de manera similar. Eliminar algunas palabras en puede, o no, resultar en un conjunto de palabras para el cual existe un u-ciclo, o u-palabra. El objetivo de este artículo es estudiar la probabilidad de existencia de los objetos universales en tal situación. Damos límites inferiores para la probabilidad en casos generales, y también derivamos respuestas explícitas para el caso de eliminar hasta dos palabras en , o el caso cuando y .
Descripción
Un ciclo universal, o u-ciclo, para un conjunto dado de palabras es una palabra circular que contiene cada palabra del conjunto exactamente una vez como una subpalabra contigua. Las celebradas secuencias de de Bruijn son un caso particular de tal u-ciclo, donde un conjunto en cuestión es el conjunto de todas las palabras de longitud sobre un alfabeto de letras. Una palabra universal, o u-palabra, es una versión lineal, es decir, no circular, de la noción de un u-ciclo, y se define de manera similar. Eliminar algunas palabras en puede, o no, resultar en un conjunto de palabras para el cual existe un u-ciclo, o u-palabra. El objetivo de este artículo es estudiar la probabilidad de existencia de los objetos universales en tal situación. Damos límites inferiores para la probabilidad en casos generales, y también derivamos respuestas explícitas para el caso de eliminar hasta dos palabras en , o el caso cuando y .