Hispanopedia Wiki
Articulo de referencia

secuencia sincronizada k

En matemáticas e informática teórica , una secuencia k -sincronizada es una secuencia infinita de términos s ( n ) caracterizada por un autómata finito que toma como entrada dos...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas e informática teórica , una secuencia k -sincronizada es una secuencia infinita de términos s ( n ) caracterizada por un autómata finito que toma como entrada dos cadenas m y n , cada una expresada en una base fija k , y acepta si m  = s ( n ). La clase de secuencias k -sincronizadas se encuentra entre las clases de secuencias k -automáticas y secuencias k -regulares . 

Definiciones

Como relaciones

Sea Σ un alfabeto de k símbolos donde k  ≥  2, y sea [ n ] k la representación en base k de algún número n . Dado r  ≥  2, un subconjunto R denorter{\displaystyle \mathbb {N} ^{r}}está k -sincronizada si la relación {([ n 1 ] k , ..., [ n r ] k )} es una relación racional [ 1 ] sincronizada a la derecha sobre Σ ∗ × ... × Σ ∗ , donde ( n 1 , ..., n r )    ∈{\displaystyle \in }R. [ 2 ]​

Teórico del lenguaje

Sea n  ≥  0 un número natural y sea f :norte→norte{\displaystyle \mathbb {N} \rightarrow \mathbb {N} }Sea un mapa, donde tanto n como f ( n ) se expresan en base k . La secuencia f ( n ) está k -sincronizada si el lenguaje de pares{(norte,F(norte))}{\displaystyle \{(n,f(n))\}}es regular .

Historia

La clase de secuencias k -sincronizadas fue introducida por Carpi y Maggi. [ 2 ]

Ejemplo

Complejidad de subpalabras

Dada una secuencia k -automática s ( n ) y una cadena infinita S  = s (1) s (2)..., sea ρ S (n) la complejidad de subpalabras de S ; es decir, el número de subpalabras distintas de longitud n en S . Goč, Schaeffer y Shallit [ 3 ] demostraron que existe un autómata finito que acepta el lenguaje 

{(norte,metro)k∣norte≥0 y metro=ρS(norte)}.{\displaystyle \{(n,m)_{k}\mid n\geq 0{\text{ y }}m=\rho _{S}(n)\}.}

Este autómata adivina los extremos de cada bloque contiguo de símbolos en S y verifica que cada subpalabra de longitud n que comienza dentro de un bloque dado sea novedosa, mientras que todas las demás subpalabras no lo sean. Luego verifica que m sea la suma de los tamaños de los bloques. Dado que el par ( n , m ) k es aceptado por este autómata, la función de complejidad de subpalabras de la secuencia k -automática s ( n ) está k -sincronizada. 

Propiedades

Las secuencias k -sincronizadas presentan una serie de propiedades interesantes. A continuación se presenta una lista no exhaustiva de estas propiedades.

  • Toda secuencia k -sincronizada es k -regular . [ 4 ]
  • Toda secuencia k -automática está k -sincronizada. Para ser precisos, una secuencia s ( n ) es k -automática si y solo si s ( n ) está k- sincronizada y toma un número finito de términos. [ 5 ] Esto es una consecuencia inmediata tanto de la propiedad anterior como del hecho de que toda secuencia k -regular que toma un número finito de términos es k -automática.
  • La clase de secuencias k -sincronizadas es cerrada bajo suma término a término y composición término a término. [ 6 ] [ 7 ]
  • Los términos de cualquier secuencia k -sincronizada tienen una tasa de crecimiento lineal. [ 8 ]
  • Si s ( n ) es una secuencia k -sincronizada, entonces tanto la complejidad de subpalabras de s ( n ) como la complejidad palindrómica de s ( n ) (similar a la complejidad de subpalabras, pero para palíndromos distintos ) son secuencias k -regulares. [ 9 ]

Notas

  1. ↑ Frougny, C.; Sakarovitch, J. (1993), "Relaciones racionales sincronizadas de palabras finitas e infinitas", Theoret. Comput. Sci. , 108 : 45–82 , doi : 10.1016/0304-3975(93)90230-Q
  2. 1 2 Carpi y Maggi (2010)
  3. ↑ Goč, D.; Schaeffer, L.; Shallit, J. (2013). Complejidad de subpalabras y k -sincronización . Lecture Notes in Computer Science. Vol. 7907. Editores Béal MP., Carton O. Berlín: Springer . ISBN  978-3-642-38770-8.
  4. ↑ Carpi y Maggi (2010), Proposición 2.6
  5. ↑ Carpi y Maggi (2010), Proposición 2.8
  6. ↑ Carpi y Maggi (2010), Proposición 2.1
  7. ↑ Carpi y Maggi (2010), Proposición 2.2
  8. ↑ Carpi y Maggi (2010), Proposición 2.5
  9. ↑ Carpi, A.; D'Alonzo, V. (2010), "Sobre factores de secuencias sincronizadas", Theoret. Comput. Sci. , 411 ( 44– 46): 3932– 3937, doi : 10.1016/j.tcs.2010.08.005

Referencias

  • Carpi, A.; Maggi, C. (2010), "Sobre secuencias sincronizadas y sus separadores" , Theoret. Informatics Appl. , 35 (6): 513– 524, doi : 10.1051/ita:2001129.