Transductor p-subsecuencial adelantado

Un Transductor p-subsecuencial adelantado es un transductor p-subsecuencial con la salida asignada a los arcos de forma que se produzca tan pronto como sea posible.

Una transducción ${\displaystyle \tau :E\rightarrow 2^{\Gamma ^{*}}}$ que asigna a cada cadena de caracteres en ${\displaystyle E\subseteq \Sigma ^{*}}$ un conjunto de cadenas de caracteres en ${\displaystyle \Gamma ^{*}}$ es ${\displaystyle p}$-subsecuencial adelantada^[1]​^[2]​^[3]​ si existe una transducción secuencial ${\displaystyle \eta }$ que:

${\displaystyle \tau (w)=\eta (w)S(w)\;\forall w\in E,\;|S(w)|\leq p}$ donde:

• ${\displaystyle S(w)\in 2^{\Gamma ^{*}}}$ es el conjunto de como máximo ${\displaystyle p}$ colas (sufijos), con

${\displaystyle \mu _{0}=\mathrm {LCP} (\tau (E))}$ ${\displaystyle \zeta (w,\sigma )=[\mathrm {LCP} (\tau (ww^{-1}E))]^{-1}[\mathrm {LCP} (\tau ((w\sigma )(w\sigma )^{-1}E))]}$ ${\displaystyle S(w)=[\mathrm {LCP} (\tau (ww^{-1}E))]^{-1}\tau (w)}$

donde:

• LCP (longest common prefix) es el prefijo común más largo
• ${\displaystyle ww^{-1}E=\{x\in E\;:\;w\in \mathrm {Pr} (x)\}}$
• ${\displaystyle (w\sigma )(w\sigma )^{-1}E=\{x\in E\;:\;w\sigma \in \mathrm {Pr} (x)\}}$.

Cada vez que un símbolo ${\displaystyle \sigma }$ se lee, la función ${\displaystyle \zeta (w,\sigma )}$ añade el sufijo más largo posible a ${\displaystyle \eta (w)}$ para formar ${\displaystyle \eta (w\sigma )}$, el prefijo actual de salida; finalmente, ${\displaystyle \tau (w)}$ se calcula concatenando el resultado de la transducción secuencial ${\displaystyle \eta }$ con el conjunto de como máximo ${\displaystyle p}$ sufijos ${\displaystyle S(w)}$ Por lo que se puede observar que las transducciones secuenciales son un caso especial de las transducciones ${\displaystyle p}$ subsecuenciales: con ${\displaystyle p=1}$ y ${\displaystyle S(w)={\varepsilon }\;\forall w\in E}$.

• Transductor de estados finitos
• Transductor secuencial
• Transductor subsecuencial
• Transductor p-subsecuencial
• Transductor de estados finitos determinista p-subsecuencial
• Transductor de estados finitos determinista p-subsecuencial adelantado