Conditional Equations - Strings

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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.

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 ist der Funktionsname
D sind Typen (Argumenttypen und Wertetyp), also beliebige Mengen
Konstantendeklaration mit:

vars Variablendeklarationen Deklaration einer Variablen in der Form (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