La complejidad máxima de palabras infinitas cuasiperiódicas
Autores: Staiger, Ludwig
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
La complejidad máxima de palabras infinitas cuasiperiódicas
Categoría
Matemáticas
Subcategoría
Análisis matemático
Palabras clave
Cadena infinita
Palabra
Complejidad
Lenguaje
Caracterización
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 20
Citaciones: Sin citaciones
Un quasiperíodo de una cadena finita o infinita es una palabra cuyas ocurrencias cubren cada parte de la cadena. Una cadena infinita se denomina cuasiperiódica si tiene un quasiperíodo. Presentamos una caracterización del conjunto de cadenas infinitas que tienen una cierta palabra como cuasiperíodo a través de un lenguaje finito que consiste en prefijos del quasiperíodo. Resulta que su raíz estelar es un código de sufijo que tiene un retraso acotado de descifrabilidad. Esto nos permite calcular la complejidad máxima de subpalabra (o factor) de cadenas infinitas cuasiperiódicas que tienen un quasiperíodo y además derivar que las cadenas infinitas cuasiperiódicas maximalmente complejas tienen quasiperíodos o . Se muestra que, para cada longitud , una palabra de la forma (o si es par) genera la cadena infinita más compleja que tiene esta palabra como quasiperíodo. Damos el orden exacto de las longitudes con respecto a la complejidad alcanzable entre todas las palabras de longitud .
Descripción
Un quasiperíodo de una cadena finita o infinita es una palabra cuyas ocurrencias cubren cada parte de la cadena. Una cadena infinita se denomina cuasiperiódica si tiene un quasiperíodo. Presentamos una caracterización del conjunto de cadenas infinitas que tienen una cierta palabra como cuasiperíodo a través de un lenguaje finito que consiste en prefijos del quasiperíodo. Resulta que su raíz estelar es un código de sufijo que tiene un retraso acotado de descifrabilidad. Esto nos permite calcular la complejidad máxima de subpalabra (o factor) de cadenas infinitas cuasiperiódicas que tienen un quasiperíodo y además derivar que las cadenas infinitas cuasiperiódicas maximalmente complejas tienen quasiperíodos o . Se muestra que, para cada longitud , una palabra de la forma (o si es par) genera la cadena infinita más compleja que tiene esta palabra como quasiperíodo. Damos el orden exacto de las longitudes con respecto a la complejidad alcanzable entre todas las palabras de longitud .