logo móvil
Contáctanos

La complejidad máxima de palabras infinitas cuasiperiódicas

Autores: Staiger, Ludwig

Idioma: Inglés

Editor: MDPI

Año: 2021

Descargar PDF

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


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 .

Otros recursos que podrían interesarte

Temas Virtualpro