blob: 7e9e9e3501a4607eb6cdac7a77847429f3d0e5e2 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
Es stellt sich die Frage, ob das obig beschriebene Verfahren zur Konstruktion einer edit-lens sich auch auf nicht determinische finite state transducers anwenden lässt.
Eine natürlich Erweiterung von \texttt{DFSTAction} wäre:
\begin{lstlisting}[language=Haskell]
data FSTAction state input output = FSTAction
{ runFSTAction :: state -> Map state [Seq output]
, fstaConsumes :: Seq input
}
\end{lstlisting}
wobei die Liste aller möglichen output-Strings in der rechten Seite von \texttt{runFSTAction} in aller Regel unendlich ist.
$\Rrightarrow$ würde sich notwendigerweise arbiträr auf einen der möglichen output-Strings festlegen, aber ansonsten wohl identisch zum DFST-Fall implementieren lassen.
$\Lleftarrow$ basiert fundamental darauf im Komplement anhand der erzeugten output-Strings zu suchen (um das betroffene Intervall im output-String auf das Komplement zu übertragen).
Um sicher zu stellen, dass jene Suche immer terminiert, müsste die Aufzählung der i.A. unendlich vielen zulässigen output-Strings in \texttt{FSTAction} geschickt gewählt sein.
Quellen von Serien unendlich vieler output-Strings sind notwendigerweise Zykel im betrachteten FST.
Wir könnten nun für jeden Zykel im betrachteten FST eine Kante arbiträr wählen und dem Folgen jener Kante Kosten zuweisen.
Wenn wir nun sicherstellen, dass output-Strings in Reihenfolge aufsteigender Kosten aufgezählt werden, lässt sich zu jedem endlichen output-String eine Eingabe in endlicher Zeit finden.
Das obig beschriebene Verfahren weißt eine Asymmetrie auf, die im unterliegenden FST nicht vorhanden ist (sowohl Eingabe- als auch Ausgabe-Symbole sind Annotationen vom gleichen Typ an die Transitionen des FST).
Diese Asymmetrie ergibt sich ausschließlich aus der Wahl des Komplements.
Wählen wir stattdessen ein Komplement, dass Eingabe und Ausgabe symmetrisch behandelt:
\begin{lstlisting}[language=Haskell]
newtype FSTAction' state input output = FSTAction'
{ runFSTAction' :: state -> Map state [Seq input, Seq output]
}
\end{lstlisting}
So lassen sich $\Rrightarrow^\prime$ und $\Lleftarrow^\prime$ ebenfalls symmetrisch, analog zu $\Lleftarrow$, konstruieren.
|
