Sequenzielle Funktion
Einfache Sprache
Eine sequenzielle Funktion ist die durch die Semantik einer Sequenzielle Maschine berechnete partiellen Funktion. Eine sequenzielle Funktion lässt sich also durch eine Sequenzielle Maschine darstellen.
Def. Sequenzielle Funktion
Eine Funktion $f:A^*\rightharpoonup B^*$ ist sequentiell genau dann wenn sie
- linear beschränktes Abstandswachstum und
- das Reguläre Urbildmengen besitzt.
Alternative kann gezeigt werden das $f$ sequentiell ist, wenn es eine Sequenzielle Maschine $M$ gibt, deren Durch die Sequenzielle Maschine berechenbare Funktion $f_M$ gleich $f$ ist, also $f_M = f$.
Alternative kann auch Lemma des linear beschränkten Längenwachstum genutzt werden um zu zeigen, dass eine Funktion sequentiell ist.
Achtung
Es gibt Funktionen, die nicht sequentiell sind, aber linear beschränktes Längenwachstum besitzen (Z.B. Funktion reverse. Nimmt man also als Widerspruchsannahme an das eine Funktion sequentiell ist und zeigt, dass sie linear beschränktes Längenwachstum hat, ist das kein Beweis, dass sie wirklich sequentiell ist.