From 8afbe1f7df24034dd16fdf2e89b0665b2318ae2a Mon Sep 17 00:00:00 2001
From: Gregor Kleen <gkleen@yggdrasil.li>
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/Lens.tex')

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

