Transductor p-subsecuencial adelantado

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

μ0 = LCP(τ(E)) ζ(w,σ) = [LCP(τ(ww − 1E))] − 1[LCP(τ((wσ)(wσ) − 1E))] S(w) = [LCP(τ(ww − 1E))] − 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


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. 

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Transductor de estados finitos determinista p-subsecuencial adelantado — Los transductores de estados finitos son Autómatas de estados finitos deterministas con transiciones sobre parejas de símbolos. Un transductor de estados finitos determinista p subsecuencial adelantado (TpSSDA o EDpSST de sus siglas en inglés… …   Wikipedia Español

  • Transductor p-subsecuencial — Un transductor p subsecuencial es un transductor subsecuencial que produce un número p de cadenas de salida adicional.[1] Se puede decir que es un transductor secuencial ampliado para permitir un número finito p de cadenas de salida en los… …   Wikipedia Español

  • Transductor subsecuencial — Un transductor subsecuencial o transductor 1 subsecuencial es aquel donde los símbolos de salida se generan sólo cuando se han visto suficientes símbolos en la entrada para garantizar una salida correcta. Se puede decir que es un transductor… …   Wikipedia Español

  • Transductor de estados finitos — Un transductor de estados finitos, o transductor finito, es un autómata finito (o máquina de estados finitos) con dos cintas, una de entrada y otra de salida. Esto contrasta con un autómata finito habitual, que tienes solamente una cinta. Podemos …   Wikipedia Español

  • Transductor de estados finitos determinista p-subsecuencial — Un transductor de estados finitos determinista p subsecuencial es un Autómata de estados finitos deterministas con transiciones sobre parejas de símbolos. Éstos transductores no tienen estados de aceptación explicitamente definidos. Cada uno de… …   Wikipedia Español

  • Transducción secuencial — Este artículo o sección tiene un estilo difícil de entender para los lectores interesados en el tema. Si puedes, por favor edítalo y contribuye a hacerlo más accesible para el público general, sin eliminar los detalles técnicos que interesan a… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”