Conditional Equations - Strings

CE-S (Conditional Equations - Strings) ist eine formale Sprache zur Modellierung von Algorithmen. Diese Sprache arbeitet auf Basis von bedingten Gleichungen, die je nach Auswertung der Bedingung gegebene Zeichenketten (Strings) mit Hilfe bestimmter Operationen manipulieren. Funktionen, die mit CE-S berechnet werden können, entsprechen den berechenbaren Funktionen nach der Church-Turing-These. Das bedeutet, dass mit Hilfe von CE-S jede Funktion berechnet werden kann, die der Mensch mit mathematischen Mitteln berechnen kann. CE-S bietet außerdem die Möglichkeit, den Aufwand für Operationen einfach zu berechnen und anschließend einer Aufwandsklasse zuzuordnen. Die Modellierung eines Algorithmus in CE-S erfolgt auf Basis der so genannten CE-S-Spezifikation.

Spezifikation

Eine CE-S-Spezifikation besteht aus folgenden Abschnitten:

Abschnitt	Bezeichnung	Erklärung
spec	Name des Algorithmus	Ein beliebiger Name
opns	Operationsdeklaration	Form einer Deklaration: $f:D_{1}\times D_{2}\times ...\times D_{a}\rightarrow D$ f ist der Funktionsname D sind Typen (Argumenttypen und Wertetyp), also beliebige Mengen Konstantendeklaration mit: $c:\rightarrow D$
vars	Variablendeklarationen	Deklaration einer Variablen in der Form $x\in D$ (getypt) x ist ein Variablenname und D ein Typ (also wieder eine beliebige Menge)
eqns	Bedingte Gleichungen	Bedingte Gleichung der Form L = R, falls b L, R sind Terme desselben Typs D b ist ein Term des Typs Boolean

Siehe auch

• Turingmaschine
• Berechenbarkeit