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

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

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

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

donde:

• LCP (longest common prefix) es el prefijo común más largo
• $ww^{-1}E=\{x\in E\;:\;w\in \mathrm {Pr} (x)\}$
• $(w\sigma )(w\sigma )^{-1}E=\{x\in E\;:\;w\sigma \in \mathrm {Pr} (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)={\varepsilon }\;\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

Referencias

• Datos: Q6151647