Transductor p-subsecuencial adelantado

Un Transductor p-subsecuencial adelatado 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 Γ ^* es p-subsecuencial adelantada^{[1] [2] [3]} si existe una transducción secuencial η 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

μ₀ = LCP(τ(E)) ζ(w,σ) = [LCP(τ(ww ^{− 1}E))] ^{− 1}[LCP(τ((wσ)(wσ) ^{− 1}E))] S(w) = [LCP(τ(ww ^{− 1}E))] ^{− 1}τ(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 σ se lee, la función ζ(w,σ) añade el sufijo más largo posible a η(w) para formar η(wσ), el prefijo actual de salida; finalmente, τ(w) se calcula concatenando el resultado de la transducción secuencial η 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

1. ↑ * Alicia Garrido-Alenda; Mikel L. Forcada (2002). «Comparing nondeterministic and quasideterministic finite-state transducers built from morphological dictionaries». Procesamiento del Lenguaje Natural. http://www.dlsi.ua.es/~mlf/docum/garrido02j.pdf. 
2. ↑ * Mehryar Mohri (1997,). «Finite-state transducers in language and speech processing,». Computational Linguistics, 23, (2,). 269--311. 
3. ↑ * J. Oncina and P. García and E. Vidal, (1993,). «Learning subsequential transducers for pattern recognition interpretation tasks,». IEEE Transactions on Pattern Analysis and Machine Intelligence, 15,. 448--458.