Transductor p-subsecuencial alvançat

Un Transductor p-subsecuencial alvançat és un transductor p-subsecuencial en l'eixida assignada als arcs de manera que es produïxca tan pronte com siga possible.

Una transducción $\tau :E\to 2^{{\Gamma }^{*}}$ que assigna a cada cadena de caràcters en $E\subseteq {\Sigma }^{*}$ un conjunt de cadenes de caràcters en ${\Gamma }^{*}$ és $p$-subsecuencial alvançada si existix una transducción seqüencial $\eta$ que:

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

• $S(w)\in 2^{{\Gamma }^{*}}$ és el conjunt de com a màxim $p$ coes (sufixos), en

${\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)$

a on:

• LCP (longest common prefix) és el prefix comú més llarc
• $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 volta que un símbol $\sigma$ es llig, la funció $\zeta (w,\sigma )$ afig el sufix més llarc possible a $\eta (w)$ per a formar $\eta (w\sigma )$, el prefix actual d'eixida; finalment, $\tau (w)$ es calcula concatenant el resultat de la transducción seqüencial $\eta$ en el conjunt de com a màxim $p$ sufixos $S(w)$ Per lo que es pot observar que les transducciones seqüencials són un cas especial de les transducciones $p$ subsecuenciales: en $p=1$ i $S(w)=\epsilon \mathrm{\forall }w\in E$.

Vore també

• Transductor d'estats finitos
• Transductor seqüencial
• Transductor subsecuencial
• Transductor p-subsecuencial
• Transductor d'estats finitos determinista p-subsecuencial
• Transductor d'estats finitos determinista p-subsecuencial alvançat