From 8afbe1f7df24034dd16fdf2e89b0665b2318ae2a Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Tue, 19 Feb 2019 11:39:51 +0100 Subject: Stuff... --- edit-lens/src/Control/FST/Lens.tex | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) create mode 100644 edit-lens/src/Control/FST/Lens.tex (limited to 'edit-lens/src/Control/FST') diff --git a/edit-lens/src/Control/FST/Lens.tex b/edit-lens/src/Control/FST/Lens.tex new file mode 100644 index 0000000..dc44e10 --- /dev/null +++ b/edit-lens/src/Control/FST/Lens.tex @@ -0,0 +1,29 @@ +Es stellt sich die Frage, ob das obig beschriebene Verfahren zur Konstruktion einer edit-lens sich auch auf nondeterminische 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 jeder endliche output-String 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. -- cgit v1.2.3