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 $\tau :E\to 2^{{\mathrm{\Gamma }}^{*}}$ que asigna a cada cadena de caracteres en $E\subseteq {\mathrm{\Sigma }}^{*}$ un conjunto de cadenas de caracteres en ${\mathrm{\Gamma }}^{*}$ es $p$-subsecuencial adelantada si existe una transducción secuencial $\eta$ que:

$\tau (w)=\eta (w)S(w)\mathrm{\forall }w\in E,|S(w)|\le p$ donde:

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

${\mu }_0=\mathrm{L}\mathrm{C}\mathrm{P}(\tau (E))$ $\zeta (w,\sigma )=[\mathrm{L}\mathrm{C}\mathrm{P}(\tau (w{w}^{-1}E)){]}^{-1}[\mathrm{L}\mathrm{C}\mathrm{P}(\tau ((w\sigma )(w\sigma {)}^{-1}E))]$ $S(w)=[\mathrm{L}\mathrm{C}\mathrm{P}(\tau (w{w}^{-1}E)){]}^{-1}\tau (w)$

donde:

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

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

Véase también

• 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