3SAT ☞ Abschnitt 7.3.4	Spezielle Variante des ☞ SAT-Problems. Für eine gegebene Menge von Klauseln mit je drei Literalen ist zu entscheiden, ob eine erfüllende Belegung existiert. Genau wie SAT gehört auch diese Fragestellung zu den ☞ NP-vollständigen Problemen. Aufgrund seiner Einfachheit wird 3SAT gerne dazu verwendet, um andere Probleme mit dem Mittel der ☞ polynomiellen Reduktion ebenfalls als NP-vollständig zu identifizieren. ▲
Abzählbarkeit ☞ Abschnitt 2.3.3	Eine Menge M heißt abzählbar, wenn sie die gleiche ☞ Mächtigkeit wie die Menge der natürlichen Zahlen besitzt. Dies ist genau dann der Fall, wenn jedes Element von M eineindeutig einer natürlichen Zahl zugeordnet werden kann. Jede aufzählbare Menge mit unendlich vielen Elementen ist auch abzählbar, nicht jedoch umgekehrt. ▲
Ackermann-Funktion ☞ Abschnitt 2.3.2	Beispiel einer Funktion, die ☞ While-berechenbar, aber nicht ☞ Loop-berechenbar ist. Ihre Existenz beweist, dass die ☞ Loop-Sprache nicht an die Stärke der meisten anderen in diesem Buch diskutierten ☞ Berechnungsmodelle herankommt. ▲
Akzeptor ☞ Abschnitt 5.2	Überbegriff für eine Reihe ☞ endlicher Automaten, die sich weiter in deterministische ( ☞ DEA) und nichtdeterministische ( ☞ NEA) Akzeptoren untergliedern lassen. In beiden Fällen bestehen die Automaten aus einer Menge von Zuständen, einem Eingabealphabet, einer Zustandsübergangsfunktion, einer Reihe von End- oder Finalzuständen sowie einem dedizierten Startzustand. In jedem Verarbeitungsschritt nimmt der Automat ein einzelnes Eingabezeichen entgegen und geht in einen neuen Zustand über. Die Eingabesequenz wird genau dann akzeptiert, wenn die Verarbeitung in einem Finalzustand endet. ▲
Allgemeingültigkeit ☞ Abschnitt 3.1.1	Eine allgemeingültige Formel besitzt die Eigenschaft, dass jede ☞ Interpretation ein ☞ Modell ist. Eine solche Formel ist damit immer wahr, unabhängig davon, wie wir ihre Bestandteile interpretieren. Der Begriff wird synonym mit dem Begriff der ☞ Tautologie verwendet. ▲
Allgemeinster Unifikator ☞ Abschnitt 3.2.3.1	Spezieller ☞ Unifikator mit der Eigenschaft, dass sich alle Unifikatoren durch die Anwendung einer weiteren Substitution erzeugen lassen. ▲
Antinomie ☞ Abschnitt 1.2.1	Spezielle Art des logischen Widerspruchs, in der die Richtigkeit einer Aussage ihre eigene Falschheit zur Folge hat und umgekehrt. In formalen Systemen führen Antinomien zu Inkonsistenzen und damit zur völligen Unbrauchbarkeit der zugrunde liegenden Axiome und Schlussregeln. Zu den bekanntesten Vertretern gehören das ☞ Barbier-Paradoxon sowie die ☞ Russell’sche Antinomie der naiven Mengenlehre. ▲
Äquivalenzproblem ☞ Abschnitt 4.1	Wichtige Problemstellung aus dem Bereich der ☞ formalen Sprachen. Hinter dem Äquivalenzproblem verbirgt sich die Frage, ob zwei Sprachen L 1 und L 2 aus den gleichen Wörtern bestehen. Mit anderen Worten: Gilt L 1 = L 2 ? ▲
Asymptotisches Wachstum ☞ Abschnitt 7.1.1	Beschreibt den Werteverlauf einer Funktion f ( n ) für den Fall n →∞. Wie sich die Funktion f ( n ) auf einem beliebigen, aber endlichen Anfangsstück verhält, spielt für das asymptotische Wachstum keine Rolle. Von konstanten Faktoren wird ebenfalls abstrahiert, so dass die Wachstumsanalyse zu einer Einteilung von Funktionen in verschiedene ☞ Komplexitätsklassen führt. Das asymptotische Wachstum ist die Grundlage, um das Laufzeitverhalten und den Speicherplatzverbrauch von Algorithmen auf einer abstrakten Ebene zu beschreiben. ▲
Aussagenlogik ☞ Abschnitt 3.1	Die Aussagenlogik beschäftigt sich mit atomaren Aussagen („Es regnet“, „Die Straße ist nass“) und den Beziehungen, die zwischen solchen Aussagen bestehen („Wenn es regnet, dann ist die Straße nass“). Die Bedeutung der Aussagenlogik ist zweigeteilt. Zum einen ist sie als Teilmenge in nahezu allen anderen Logiken enthalten, unter anderem auch in der ☞ Prädikatenlogik und den ☞ Logiken höherer Stufe. Zum anderen spielt sie eine wichtige Rolle im Hardware-Entwurf, da sich jede kombinatorische Digitalschaltung mit Hilfe aussagenlogischer Formeln beschreiben lässt. ▲
Automatenminimierung ☞ Abschnitt 5.2.2	Verfahren, um die Anzahl der Zustände eines ☞ endlichen Automaten zu verringern, ohne die nach außen sichtbare Funktion zu verändern. Ein Automat heißt reduziert, wenn kein funktional äquivalenter Automat existiert, der weniger Zustände besitzt. ▲
Automatensynthese ☞ Abschnitt 5.6.3	Bezeichnet die Umsetzung eines ☞ endlichen Automaten in ein Schaltungsmodell, das aus Speicherelementen und Logikgattern besteht. Die Automatensynthese ist ein wesentlicher Arbeitsschritt im Entwurfsprozess digitaler Hardware-Schaltungen. ▲
Axiom ☞ Abschnitt 3.1.3.1	Zentraler Bestandteil eines ☞ Hilbert-Kalküls. Axiome bilden den Ausgangspunkt eines formalen Beweises und müssen per Definition nicht selbst abgeleitet werden. In einem formalen Beweis wird die zu zeigende Aussage durch die sukzessive Anwendung fest definierter ☞ Schlussregeln aus den Axiomen deduziert. ▲
Backus-Naur-Form ☞ Abschnitt 4.4.2.2	Spezielle Notation zur Beschreibung ☞ kontextfreier Sprachen. Die Backus-Naur-Form wurde erstmals zur Spezifikation der Sprache Algol60 eingesetzt und hat sich heute als De-facto-Standard für die Syntaxdefinition von Programmiersprachen etabliert. ▲
Barbier-Paradoxon ☞ Abschnitt 2.5	Bildhafte ☞ Antinomie, die das Problem der Selbstbezüglichkeit anschaulich demonstriert. Der Barbier von Sevilla rasiert alle Männer von Sevilla, die sich nicht selbst rasieren. Die inutitive Annahme, dass der Barbier sich entweder selbst oder nicht selbst rasiert, wird durch einen Ringschluss stets zu Widerspruch geführt. Das Paradoxon entspricht im Kern der ☞ Russell’schen Antinomie, mit der die Mathematik zu Beginn des zwanzigsten Jahrhunderts in ihre bislang größte Krise gestürzt wurde. ▲
Berechenbarkeit ☞ Abschnitt 6.1	Eine Funktion f heiß berechenbar, falls ein systematisches Verfahren existiert, das für alle Eingaben x nach endlich vielen Schritten terminiert und den Funktionswert f ( x ) als Ausgabe liefert. Was wir unter einem systematischen Verfahren zu verstehen haben, wird durch die Definition eines ☞ Berechnungsmodells formal festgelegt. Der Begriff der berechenbaren Funktion ist eng mit dem Begriff der ☞ Entscheidbarkeit gekoppelt. ▲
Berechenbarkeitstheorie ☞ Kapitel 6	Teilgebiet der theoretischen Informatik, das sich mit den formalen Grundlagen und den Grenzen der algorithmischen Methode befasst. Im Gegensatz zur ☞ Komplexitätstheorie steht die prinzipielle ☞ Berechenbarkeit einer Funktion im Vordergrund und nicht die Effizienz der Lösung. Eine zentrale Erkenntnis der Berechenbarkeitstheorie ist die Existenz unberechenbarer Funktionen ( ☞ Halteproblem). ▲
Berechnungsmodell ☞ Abschnitt 6.1	Formales Konstrukt, um den Begriff der ☞ Berechenbarkeit mathematisch präzise zu erfassen. In der Vergangenheit wurden zahlreiche Berechnungsmodelle postuliert, die sich von außen betrachtet erheblich voneinander unterscheiden. Einige besitzen durch und durch mathematischen Charakter, während sich andere sehr nahe an der Hardware-Architektur realer Computersysteme orientieren. Die ☞ primitiv-rekursiven Funktionen, die ☞ μ-rekursiven Funktionen und das Lambda-Kalkül gehören zur ersten Gruppe, die ☞ Loop-, ☞ Goto- und ☞ While-Sprache sowie die ☞ Turing-Maschine und die ☞ Register-Maschine zur zweiten. ▲
Bisimulation ☞ Abschnitt 5.2.2	Spezielle Äquivalenzrelation auf der Zustandsmenge eines ☞ endlichen Automaten. Zwei Zustände s 1 und s 2 sind genau dann bisimulativ zueinander, wenn sich der Automat für alle zukünftigen Eingaben gleich verhält, unabhängig davon, ob er sich in s 1 oder s 2 befindet. Die Bestimmung bisimulativer Zustände ist eine Kernaufgabe in der ☞ Automatenminimierung. ▲
Charakteristische Funktion ☞ Abschnitt 6.4	Mathematisches Konstrukt, das den Zusammenhang zwischen der ☞ Berechenbarkeit einer Funktion und der ☞ Entscheidbarkeit einer Menge herstellt. Eine Menge M ist genau dann entscheidbar, wenn die charakteristische Funktion χ M berechenbar ist. Ein Spezialfall ist die partielle charakteristische Funktion, die direkt zum Begriff der ☞ Semi-Entscheidbarkeit führt. ▲
Chomsky-Hierarchie ☞ Abschnitt 4.2	Rangfolge von Klassen formaler ☞ Grammatiken. Anhand der Struktur der Produktionsregeln wird eine Grammatik einer von vier Klassen zugeordnet. Typ-0-Grammatiken unterliegen keinerlei Einschränkung und definieren die Sprachklasse der rekursiv aufzählbaren Sprachen. Typ-1- und Typ-2-Grammatiken erzeugen die ☞ kontextsensitiven und die ☞ kontextfreien Sprachen. ☞ Reguläre Sprachen werden von Typ-3-Grammatiken erzeugt. Zwischen den Sprachklassen besteht eine Inklusionsbeziehung, d. h., jede Typ-3-Sprache ist auch eine Typ-2-Sprache und so fort. Ferner existieren in jeder Klasse Sprachen, die in der eingebetteten Klasse nicht enthalten sind. ▲
Chomsky-Normalform ☞ Abschnitt 4.4.2.1	Spezielle Darstellungsform für Typ-2-Grammatiken. Zu jeder ☞ kontextfreien Sprache L existiert eine ☞ Grammatik in Chomsky-Normalform, die L erzeugt. Die Chomsky-Normalform ist eng verwandt mit der ☞ Greibach-Normalform. ▲
Church’sche These ☞ Abschnitt 6.2	Von Alonzo Church aufgestellte These über den Berechenbarkeitsbegriff. Sie besagt, dass die Klasse der Turing-berechenbaren Funktionen mit der Klasse der intuitiv berechenbaren Funktionen übereinstimmt. Mit anderen Worten: Jede Funktion, die überhaupt in irgendeiner Weise berechenbar ist, kann auch durch eine ☞ Turing-Maschine berechnet werden. Die These wird durch die Beobachtung gestützt, dass alle hinreichend berechnungsstarken Modelle wie die ☞ While-Sprache, die ☞ Goto-Sprache, die ☞ μ-Rekursion oder die ☞ Registermaschine exakt den gleichen Berechenbarkeitsbegriff definieren. ▲
Co-Komplexität ☞ Abschnitt 7.2.4	Zu jeder ☞ Komplexitätsklasse C existiert die komplementäre Komplexitätsklasse coC. Eine Sprache L gehört genau dann zu coC, wenn das Komplement L zu C gehört. Die co-Komplexität spielt nur im Bereich nichtdeterministischer Komplexitätsklassen eine Rolle. Für jede deterministische Komplexitätsklasse C gilt die Beziehung C = co C. ▲
CYK-Algorithmus ☞ Abschnitt 4.4.4	Nach John Cocke, Daniel Younger und Tadao Kasami benannter Algorithmus zur Lösung des ☞ Wortproblems ☞ kontextfreier Sprachen. Der Algorithmus basiert auf dem Verfahren der ☞ dynamischen Programmierung. Ausgangspunkt ist eine ☞ Grammatik G in ☞ Chomsky-Normalform. ▲
DEA ☞ Abschnitt 5.2	Deterministischer endlicher ☞ Akzeptor. Im Gegensatz zu seinem nichtdeterministischen Pendant ( ☞ NEA) ist der auszuführende Zustandsübergang für jedes Eingabezeichen eindeutig definiert. Die von DEAs und NEAs akzeptierte Sprachklasse ist identisch und entspricht der Klasse der ☞ regulären Sprachen. ▲
Diagonalisierung ☞ Abschnitt 2.3.3	Mathematisches Beweisverfahren, um Aussagen über die Mächtigkeit zweier Mengen zu verifizieren. Unter anderem kann mit der Methode die Gleichmächtigkeit von ℕ und ℚ gezeigt (erstes Cantor’sche Diagonalargument) oder die Menge ℝ als überabzählbar entlarvt werden (zweites Cantor’sches Diagonalargument). In Kapitel ?? wurde die Diagonalisierung eingesetzt, um die ☞ Unentscheidbarkeit des allgemeinen ☞ Halteproblems zu beweisen. ▲
Dirichlet’sches Schubfachprinzip ☞ Abschnitt 3.1.1	Mathematische Schlussregel aus dem Bereich der diskreten Mathematik. Plakativ beschreibt sie den folgenden Sachverhalt: Werden n +1 Gegenstände auf n Fächer verteilt, so enthält mindestens ein Fach mehr als einen Gegenstand. In der Literatur wird das Dirichlet’sche Schubfachprinzip auch als Taubenschlagprinzip bezeichnet, in Anlehnung an den englischen Begriff pigeonhole principle. ▲
Disjunktive Form ☞ Abschnitt 3.1.2	Eine Logikformel liegt in disjunktiver Form vor, wenn sie als Disjunktion von Konjunktionen aufgebaut ist. ▲
Disjunktive Normalform ☞ Abschnitt 3.1.2	Eine Logikformel liegt in disjunktiver Normalform vor, wenn sie als Disjunktion von ☞ Mintermen aufgebaut ist und alle Minterme paarweise verschieden sind. ▲
Dynamische Programmierung ☞ Abschnitt 4.4.4	Spezielles Konstruktionsprinzip für Algorithmen. Die dynamische Programmierung kann immer dann eingesetzt werden, wenn sich die optimale Lösung eines Problems aus den optimalen Lösungen seiner Teilprobleme zusammensetzen lässt. Ein bekannter Algorithmus, der nach diesem Prinzip arbeitet, ist der ☞ CYK-Algorithmus zur Lösung des ☞ Wortproblems ☞ kontextfreier Sprachen. Auch das ☞ Rucksackproblem lässt sich mit dem Prinzip der dynamischen Programmierung effizient lösen. ▲
Endlicher Automat ☞ Kapitel 5	Mathematisches Modell zur Beschreibung zustandsbasierter Systeme. Entsprechend ihrer Funktionsweise werden endliche Automaten in ☞ Akzeptoren und ☞ Transduktoren eingeteilt. Akzeptoren sind ein wichtiges Hilfsmittel für die Analyse ☞ formaler Sprachen. Transduktoren sind die theoretische Grundlage für die Modellierung jeglicher Computer-Hardware. ▲
Endlichkeitsproblem ☞ Abschnitt 4.1	Wichtige Problemstellung aus dem Bereich der ☞ formalen Sprachen. Hinter dem Endlichkeitsproblem verbirgt sich die Frage, ob eine Sprache L über einen endlichen Wortschatz verfügt. Mit anderen Worten: Gilt | L | < ∞? ▲
Entscheidbarkeit ☞ Abschnitt 6.4	Eine Menge M heißt entscheidbar, falls die ☞ charakteristische Funktion ☞ berechenbar ist. Für eine entscheidbare Menge M existiert ein systematisches Verfahren, das für alle Eingaben ω nach endlicher Zeit beantwortet, ob ω ein Element von M ist oder nicht. Heute wissen wir, dass zahllose ☞ unentscheidbare Mengen existieren. Kurzum: Der algorithmischen Methode sind unüberwindbare Grenzen gesetzt. ▲
Epsilon- Übergang ☞ Abschnitt 5.3.3	Spontaner Zustandsübergang in einem ☞ endlichen Automaten, der kein Eingabezeichen konsumiert. Epsilon-Übergänge (kurz ϵ-Übergänge) erleichtern die Konstruktion von ☞ Akzeptoren für viele ☞ reguläre Sprachen, führen aber zu keiner grundlegenden Veränderung des Automatenmodells. Jeder ϵ-Automat lässt sich in einen äquivalenten Automaten übersetzen, der keine ϵ-Übergänge mehr besitzt. ▲
Erfüllbarkeit ☞ Abschnitt 3.1.1	Eine erfüllbare Formel besitzt die Eigenschaft, dass mindestens eine ☞ Interpretation auch ein ☞ Modell ist. Eine wichtige Teilmenge der erfüllbaren Formeln sind die ☞ Tautologien. ▲
Erfüllbarkeitsäquivalenz ☞ Abschnitt 3.2.2	Zwei Formeln heißen erfüllbarkeitsäquivalent, wenn aus der ☞ Erfüllbarkeit der einen die Erfüllbarkeit der anderen folgt. Zwei äquivalente Formeln sind immer auch erfüllbarkeitsäquivalent, aber nicht umgekehrt. ▲
EXP ☞ Abschnitt 7.2.3	Die ☞ Komplexitätsklasse EXP enthält alle Sprachen, die von deterministischen ☞ Turing-Maschinen in exponentieller Zeit entschieden werden können. ▲
Formale Sprache ☞ Abschnitt 4.1	Menge von Wörtern, die über einem endlichen Alphabet Σ gebildet werden. Formale Sprachen lassen sich mit Hilfe von ☞ Grammatiken generativ erzeugen und anhand der ☞ Chomsky-Hierarchie in verschiedene Klassen einteilen. Wichtige Fragestellungen in der Theorie der formalen Sprachen sind das ☞ Wortproblem, das ☞ Leerheitsproblem, das ☞ Äquivalenzproblem und das ☞ Endlichkeitsproblem. ▲
Formales System ☞ Abschnitt 3.1.3	In diesem Buch wird der Begriff des formalen Systems synonym mit dem Begriff des ☞ Kalküls verwendet. Leider hat sich diese Terminologie in der Literatur nicht einheitlich durchgesetzt. So wird ein formales System in einigen Büchern nur dann als Kalkül bezeichnet, wenn es spezielle Eigenschaften wie z. B. die Forderung nach einer endlichen Anzahl von ☞ Axiomen oder ☞ Schlussregeln erfüllt. ▲
Gilmore-Algorithmus ☞ Abschnitt 3.2.3	Beweisverfahren für Formeln der ☞ Prädikatenlogik. Der Gilmore-Algorithmus zeigt die ☞ Allgemeingültigkeit einer Formel F, indem schrittweise die Menge der ☞ Grundinstanzen von ¬ F approximiert wird. Ist die erzeugte Teilmenge im aussagenlogischen Sinne ☞ unerfüllbar, so ist nach dem ☞ Satz von Herbrand auch die Formel ¬ F unerfüllbar. Aus der Unerfüllbarkeit von F folgt sofort die Allgemeingültigkeit von F . ▲
Gödelisierung ☞ Abschnitt 6.1.5.6	Eine injektive Funktion c : M → ℕ heißt Gödelisierung, wenn die Bildmenge c ( M ) ☞ entscheidbar und neben c auch die Umkehrfunktion c - 1 ☞ berechenbar ist. c ( x ) heißt die Gödelnummer des Elements x, geschrieben als ⟨ x ⟩. Die Gödelisierung erlaubt es, Aussagen über Objekte einer ☞ abzählbaren Menge M in Aussagen über die natürlichen Zahlen zu übersetzen. ▲
Goto-Programm ☞ Abschnitt 6.1.3	Programm, verfasst in der fiktiven ☞ Goto-Sprache. Der bedingte Sprungbefehl (If-Goto) ist die einzige Möglichkeit, den Kontrollfluss zu steuern. Nach der ☞ Church’schen These lässt sich jede intuitiv berechenbare Funktion mit Hilfe eines Goto-Programms berechnen. ▲
Goto-Sprache ☞ Abschnitt 6.1.3	Menge aller ☞ Goto-Programme. Nach der ☞ Church’schen These sind alle intuitiv berechenbaren Funktionen f Goto-berechenbar, d. h., es existiert ein Goto-Programm, das x als Eingabe entgegennimmt und f ( x ) als Ausgabe liefert. Die Goto-Sprache besitzt die gleiche Berechnungsstärke wie die ☞ While-Sprache, die ☞ Turing-Maschine, die ☞ Registermaschine und die ☞ μ-rekursiven Funktionen. ▲
Grammatik ☞ Abschnitt 4.1	Instrumentarium zur generativen Beschreibung ☞ formaler Sprachen. Die Wörter einer Sprache werden aus einem Startsymbol durch die Anwendung verschiedener Produktionsregeln abgeleitet. Abhängig von der Struktur der einzelnen Produktionen werden Grammatiken in vier disjunkte Klassen eingeteilt. Es entsteht die sogenannte ☞ Chomsky-Hierarchie. ▲
Greibach-Normalform ☞ Abschnitt 4.7	Verallgemeinerung der Bildungsregeln ☞ regulärer Grammatiken. Es lässt sich zeigen, dass jede von einer Greibach-Grammatik erzeugte Sprache kontextfrei ist. Umgekehrt existiert zu jeder ☞ kontextfreien Sprache L mit ϵ ⁄∈ L eine erzeugende Grammatik in Greibach-Normalform. Eine weitere wichtige Darstellungsvariante für Typ-2-Sprachen ist die ☞ Chomsky-Normalform. ▲
Grundinstanz ☞ Abschnitt 3.2.3	Sei F eine Formel der ☞ Prädikatenlogik. Eine Grundinstanz entsteht, indem alle Variablen durch Terme ersetzt werden, die ausschließlich Funktions- und Konstantensymbole aus F enthalten. ▲
Halteproblem ☞ Abschnitt 6.5	Synonym für die Frage, ob für jede ☞ Turing-Maschine T und jedes Eingabewort ω algorithmisch entschieden werden kann, ob T unter Eingabe von ω terminiert. Die ☞ Berechenbarkeitstheorie lehrt uns, dass das Halteproblem ☞ unentscheidbar ist und ein solches Entscheidungsverfahren aus fundamentalen Überlegungen heraus nicht existieren kann. Mit Hilfe der ☞ Reduktionstechnik lassen sich weitere ☞ unentscheidbare Probleme identifizieren. Hierzu gehören das ☞ Halteproblem auf leerem Band, das ☞ spezielle Halteproblem und das ☞ Post’sche Korrespondenzproblem. Die Verallgemeinerung des Halteproblems führt auf direkten Weg zum berühmten ☞ Satz von Rice. ▲
Halteproblem auf leerem Band ☞ Abschnitt 6.5	Synonym für die Frage, ob für jede ☞ Turing-Maschine T algorithmisch entschieden werden kann, ob T unter Eingabe von ϵ terminiert. Das Halteproblem auf leerem Band ist ☞ unentscheidbar. ▲
Hamilton-Problem ☞ Abschnitt 1.2.4	Bekanntes Problem aus der Graphentheorie. Untersucht wird die Frage, ob in einem Graphen G ein geschlossener Weg existiert, der alle Knoten genau einmal besucht. Das Hamilton-Problem ist ☞ NP-vollständig und damit Teil einer großen Klasse schwer zu lösender Probleme. Für die ☞ Komplexitätstheorie ist es von Interesse, da eine geringfügige Änderung der Aufgabenstellung zu einem Problem führt, das in linearer Zeit gelöst werden kann ( ☞ Königsberger Brückenproblem). ▲
Herbrand-Interpretation ☞ Abschnitt 3.2.3	Spezielle ☞ Interpretation für Formeln der ☞ Prädikatenlogik, in der die Variablen- und Funktionssymbole durch Elemente des ☞ Herbrand-Universums interpretiert werden. ▲
Herbrand-Universum ☞ Abschnitt 3.2.3	Das Herbrand-Universum einer prädikatenlogischen Formel F ist die Menge aller variablenfreier Terme, die mit den Funktionssymbolen von F gebildet werden können. ▲
Herbrand-Modell ☞ Abschnitt 3.2.3	Ist eine ☞ Herbrand-Interpration ein ☞ Modell einer Formel F, so sprechen wir von einem Herbrand-Modell. Alle prädikatenlogischen Kalküle beruhen auf der Eigenschaft, dass eine Formel F genau dann erfüllbar ist, wenn sie ein Herbrand-Modell besitzt. ▲
Hilbert-Kalkül ☞ Abschnitt 3.1.3	Spezielle ☞ Kalküle, die sich an der traditionellen mathematischen Beweisführung orientieren. In einem Hilbert-Kalkül werden wahre Aussagen aus einer Menge von Axiomen durch die sukzessive Anwendung fest definierter Schlussregeln abgeleitet. Ein Beweis ist eine Folge von ☞ Tautologien, an deren Ende die Behauptung steht. Hilbert-Kalküle sind von hohem theoretischen Interesse, spielen in der Praxis dagegen kaum eine Rolle. Hier kommen fast ausschließlich ☞ Widerspruchskalküle zum Einsatz, in denen sich die ☞ Allgemeingültigkeit einer Formel mit weniger Aufwand beweisen lässt. ▲
Induktionsaxiom ☞ Abschnitt 2.3.1	Name des fünften ☞ Peano-Axioms. Seine Aussage lautet wie folgt: Enthält eine Teilmenge M von ℕ die Zahl 1 und zu jedem Element n auch ihren Nachfolger n ′, so gilt M = ℕ. Aus dem Induktionsaxiom erwächst das Beweisprinzip der ☞ vollständigen Induktion. ▲
Interpretation ☞ Abschnitt 3.1.1	Spezielle Abbildung, die den Symbolen einer Logikformel eine Bedeutung zuordnet. Interpretationen sind das Bindeglied zwischen der ☞ Syntax und der ☞ Semantik einer ☞ Logik. ▲
Inzidenzmatrix ☞ Abschnitt 5.7	Matrix der Größe m × n, die das Schaltverhalten eines ☞ Petri-Netzes mit m Stellen und n Transitionen beschreibt. Für jede Stelle existiert eine eigene Zeile und für jede Transition eine eigene Spalte. Der Wert ( i,j ) besagt, wie sich die Anzahl der Marken in der Stelle S i ändert, wenn die Transition T j schaltet. Durch die Multiplikation mit dem ☞ Parikh-Vektor lässt sich die Folgekonfiguration berechnen. ▲
Kalkül ☞ Abschnitt 3.1.3	Regelsystem , mit dem die Allgemeingültigkeit einer Logikformel auf ☞ syntaktischer Ebene bewiesen werden kann. Die Durchführung eines Beweises verläuft rein maschinell und kommt ohne Meta-Wissen über ☞ Interpretationen oder ☞ Modelle aus. In der ☞ Aussagenlogik und ☞ Prädikatenlogik spielen die ☞ Hilbert-Kalküle, der ☞ Resolutionskalkül und der ☞ Tableaukalkül eine hervorgehobene Rolle. Die beiden letztgenannten fallen in die Klasse der ☞ Widerspruchskalküle. In diesem Buch wird der Begriff des Kalküls synonym mit dem Begriff des ☞ formalen Systems verwendet. ▲
Kardinalzahl ☞ Abschnitt 2.3.3	Maß für die ☞ Mächtigkeit einer Menge. Die Kardinalzahl einer endlichen Menge mit n Elementen entspricht n. Unendliche Mengen lassen sich bez. ihrer Mächtigkeit in Äquivalenzklassen einteilen, die durch die Kardinalzahlen ℵ 0 , ℵ 1 , … repräsentiert werden. ℵ (Aleph) ist der erste Buchstabe des hebräischen Alphabets. ▲
Kellerautomat ☞ Abschnitt 5.5	Spezieller ☞ endlicher Automat, der neben einer endlichen Zustandsmenge einen ☞ Kellerspeicher besitzt. Durch den hinzugefügten Speicher gewinnen Kellerautomaten im Vergleich zu DEAs oder NEAs an Ausdrucksstärke hinzu. Die Klasse der von Kellerautomaten akzeptierten Sprachen entspricht der Klasse der ☞ kontextfreien Sprachen. ▲
Kellerspeicher ☞ Abschnitt 5.5	Unendlich großer Speicher, der nach dem FIFO-Prinzip arbeitet. Die Abkürzung FIFO steht für First In, First Out und bedeutet, dass immer nur das oberste Kellerzeichen manipuliert werden kann. ▲
Klausel ☞ Abschnitt 3.1.2	Eine Klausel ist eine Menge von ☞ Literalen { ( ¬ ) A 1 , … , ( ¬ ) A i } und steht stellvertretend für die Formel ( ¬ ) A 1 ∨ … ∨ ( ¬ ) A i . Die leere Klausel □ repräsentiert den Wahrheitswert 0. ▲
Kleene’sche Normalform ☞ Abschnitt 6.1.3	Spezielle Darstellungsform für ☞ While-Programme, die mit einer einzigen While-Schleife auskommen. Nach dem ☞ Satz von Kleene existiert für jedes While-Programm ein äquivalentes Programm in Kleene’scher Normalform. ▲
Komplexitätsklasse ☞ Abschnitt 7.1.1	In der ☞ Komplexitätstheorie werden Funktionen anhand ihres ☞ asymptotischen Wachstums in verschiedene Komplexitätsklassen eingeteilt. Für deren Beschreibung wird die ☞ O-Notation verwendet. Komplexitätsklassen werden eingesetzt, um die Laufzeit und den Platzverbrauch von Algorithmen zu kategorisieren. Von besonderer Bedeutung sind die Klassen ☞ P, ☞ NP, ☞ EXP, ☞ NEXP, ☞ PSPACE und ☞ NPSPACE. Zu jeder Komplexitätsklasse C existiert eine komplementäre Komplexitätsklasse coC ( ☞ Co-Komplexität). ▲
Komplexitätstheorie ☞ Kapitel 7	Teilgebiet der theoretischen Informatik, das sich mit der Frage beschäftigt, wie sich Algorithmen für sehr große Eingaben verhalten. Hierzu werden Algorithmen anhand ihres Speicherplatzbedarfs und Zeitverbrauchs in verschiedene Komplexitätsklassen eingeteilt, die Rückschlüsse auf das asymptotische Wachstum der untersuchten Parameter zulassen. Im Gegensatz zur ☞ Berechenbarkeitstheorie, die Fragen nach der puren Existenz von Berechnungsverfahren beantwortet, stellt die Komplexitätstheorie die praktische Verwertbarkeit von Algorithmen in den Vordergrund. ▲
Konfiguration ☞ Abschnitt 5.2	Momentaufnahme eines ☞ endlichen Automaten oder einer ☞ Turing-Maschine. Der Konfigurationsbegriff ist ein technisches Hilfsmittel, um Zustandsübergänge und die hieraus resultierende Ableitungsrelation in mathematisch präziser Form zu charakterisieren. ▲
Königsberger Brückenproblem ☞ Abschnitt 1.2.4	Bekanntes Problem aus der Graphentheorie. Untersucht wird die Frage, ob in einem Graphen G ein geschlossener Weg existiert, der alle Kanten genau einmal besucht. Leonhard Euler konnte zeigen, dass das Problem in linearer Zeit gelöst werden kann. Für die ☞ Komplexitätstheorie ist es von Interesse, da eine geringfügige Änderung der Aufgabenstellung ein ☞ NP-vollständiges Problem entstehen lässt ( ☞ Hamilton-Problem). ▲
Konjunktive Form ☞ Abschnitt 3.1.2	Eine Logikformel liegt in konjunktiver Form vor, wenn sie als Konjunktion von Disjunktionen aufgebaut ist. ▲
Konjunktive Normalform ☞ Abschnitt 3.1.2	Eine Logikformel liegt in konjunktiver Normalform vor, wenn sie als Konjunktion von ☞ Maxtermen aufgebaut ist und alle Maxterme paarweise verschieden sind. ▲
Kontextfreie Grammatik ☞ Abschnitt 4.2	Grammatik mit der Eigenschaft, dass die linke Seite einer Produktionsregel ausschließlich aus einer einzigen Variablen besteht. In der Nomenklatur der ☞ Chomsky-Hierarchie werden kontextfreie Grammatiken als Typ-2-Grammatiken bezeichnet. ▲
Kontextfreie Sprache ☞ Abschnitt 4.2	Eine Sprache L heißt kontextfrei, falls eine ☞ kontextfreie Grammatik existiert, die L erzeugt. Die Menge der kontextfreien Sprachen entspricht der Menge der von ☞ Kellerautomaten akzeptierten Sprachen. ▲
Kontextsensitive Grammatik ☞ Abschnitt 4.2	Grammatik mit der Eigenschaft, dass die Anwendung einer Produktion niemals zu einer Verkürzung der abgeleiteten Zeichenkette führt. In der Nomenklatur der ☞ Chomsky-Hierarchie werden kontextsensitive Grammatiken als Typ-1-Grammatiken bezeichnet. ▲
Kontextsensitive Sprache ☞ Abschnitt 4.2	Eine Sprache L heißt kontextsensitiv, falls eine ☞ kontextsensitive Grammatik existiert, die L erzeugt. Die Menge der kontextsensitiven Sprachen entspricht der Menge der Sprachen, die von linear beschränkten ☞ Turing-Maschinen akzeptiert werden. ▲
Landau-Symbole ☞ Abschnitt 7.1.1	Bezeichnung für die Symbolmenge {O, Ω , Θ ,o,ω }. Die Landau-Symbole werden in der ☞ O-Notation verwendet, um das ☞ asymptotische Wachstum von Funktionen zu beschreiben. ▲
Leerheitsproblem ☞ Abschnitt 4.1	Wichtige Problemstellung aus dem Bereich der ☞ formalen Sprachen. Hinter dem Leerheitsproblem verbirgt sich die Frage, ob eine gegebene Sprache L mindestens ein Wort enthält. Mit anderen Worten: Gilt L ≠ ∅? ▲
Linksableitung ☞ Abschnitt 4.1	Ableitungssequenz mit der Eigenschaft, dass in jedem Schritt das am weitesten links stehende Nonterminal ersetzt wurde. ▲
Literal ☞ Abschnitt 3.1.2	Bezeichnung für eine atomare Formel oder deren Negation. In der Aussagenlogik hat ein Literal damit die Form A oder ¬ A, wobei A eine beliebige aussagenlogische Variable bezeichnet. ▲
Logik ☞ Kapitel 3	Teilbereich der Mathematik, der sich mit grundlegenden Fragestellungen mathematischer Theorien beschäftigt. Ferner wird der Begriff für die Beschreibung von formalen Systemen verwendet, in denen die ☞ Syntax und die ☞ Semantik strikten Regeln folgen. In der Vergangenheit wurden verschiedene Logiken postuliert, die sich sowohl in ihrem Erscheinungsbild als auch in ihrer Ausdrucksstärke erheblich voneinander unterscheiden. Wichtige Vertreter sind die ☞ Aussagenlogik, die ☞ Prädikatenlogik sowie die ☞ Logiken höherer Stufe. ▲
Logik höherer Stufe ☞ Abschnitt 3.3	Erweiterung der ☞ Prädikatenlogik, die unter anderem stark genug ist, um die natürlichen Zahlen zu beschreiben. Im Gegensatz zur Prädikatenlogik dürfen in Logiken höherer Stufe auch Teilmengen des Grundbereichs, d. h. auch Prädikate quantifiziert werden. Erst hierdurch wird es möglich, das für die Formalisierung der natürlichen Zahlen unabdingbare ☞ Induktionsaxiom innerhalb der Logik auszudrücken. Logiken höherer Stufe werden in denjenigen Bereichen der formalen Hard- und Software-Verifikation eingesetzt, die eine hohe Ausdrucksstärke benötigen. ▲
Loop-Programm ☞ Abschnitt 6.1.1	Programm, verfasst in der fiktiven ☞ Loop-Sprache. Die Loop-Schleife ist die einzige Möglichkeit, den Kontrollfluss zu steuern. Anders als in einem ☞ While-Programm steht die Anzahl der auszuführenden Iterationen vor dem Schleifeneintritt fest und kann danach nicht mehr verändert werden. ▲
Loop-Sprache ☞ Abschnitt 6.1.1	Menge aller ☞ Loop-Programme. Die Loop-Sprache ist berechnungsschwächer als die ☞ While-Sprache oder die ☞ Goto-Sprache. So lässt sich beispielsweise die ☞ Ackermann-Funktion mit Hilfe eines ☞ While-Programms oder eines ☞ Goto-Programms berechnen, nicht jedoch mit einem Loop-Programm. ▲
Mächtigkeit ☞ Abschnitt 2.3.3	Mathematisches Konstrukt, das quantitative Aussagen über die Anzahl der Elemente beliebig großer Mengen gestattet. Die Mächtigkeit endlicher Mengen wird mit der Anzahl ihrer Elemente gleichgesetzt. Unendliche Mengen werden bez. ihrer Eigenschaft untersucht, bijektiv auf andere Mengen mit bekannter Mächtigkeit abbildbar zu sein. Auf diese Weise entsteht eine Hierarchie verschiedener Unendlichkeiten, die sich mit Hilfe von ☞ Kardinalzahlen eindeutig beschreiben lassen. ▲
Maxterm ☞ Abschnitt 3.1.2	Aussagenlogische Formel, die für genau eine Variablenbelegung falsch wird. Ein Maxterm einer Funktion mit n Variablen besteht aus n disjunktiv verknüpften ☞ Literalen. ▲
Mealy-Automat ☞ Abschnitt 5.6.4	Spezieller ☞ Transduktor, der die Ausgabe sowohl aus dem aktuellen Zustand als auch aus der aktuellen Eingabe berechnet. Mealy-Automaten werden aufgrund dieser Eigenschaft auch als Übergangsautomaten bezeichnet. ▲
Mehrdeutigkeitsproblem ☞ Abschnitt 4.1	Wichtige Problemstellung aus dem Bereich der ☞ formalen Sprachen. Hinter dem Mehrdeutigkeitsproblem verbirgt sich die Frage, ob die Ableitungssequenzen einer Grammatik G stets eindeutig sind. In mehrdeutigen Grammatiken existiert mindestens ein Wort ω, das sich durch unterschiedliche Regelanwendungen aus dem Startsymbol S ableiten lässt. ▲
Minterm ☞ Abschnitt 3.1.2	Aussagenlogische Formel, die für genau eine Variablenbelegung wahr wird. Ein Minterm einer Funktion mit n Variablen besteht aus n konjunktiv verknüpften ☞ Literalen. ▲
Modell ☞ Abschnitt 3.1.1	Spezielle ☞ Interpretation, die eine gegebene logische Formel wahr werden lässt. ▲
Modus ponens ☞ Abschnitt 3.1.3	Elementare Schlussregel der mathematischen Logik, die sich in Worten wie folgt umschreiben lässt: Wenn die Aussage A wahr ist und aus A die Aussage B folgt, so ist auch B wahr. Der Modus ponens ist die bevorzugte Schlussregel in den meisten ☞ Hilbert-Kalkülen. ▲
Moore-Automat ☞ Abschnitt 5.6.4	Spezieller ☞ Transduktor, der die aktuelle Ausgabe ausschließlich aus dem aktuellen Zustand berechnet. Moore-Automaten werden aufgrund dieser Eigenschaft auch als Zustandsautomaten bezeichnet. ▲
μ-rekursive Funktion ☞ Abschnitt 6.1.4	Kleinste Menge, die alle ☞ primitiv-rekursiven Funktionen enthält und außerdem unter der Anwendung des μ-Operators abgeschlossen ist. Die μ-rekursiven Funktionen besitzen die gleiche Berechnungsstärke wie die ☞ While-Sprache, die ☞ Goto-Sprache, die ☞ Turing-Maschine und die ☞ Registermaschine. Nach der ☞ Church’schen These ist jede intuitiv berechenbare Funktion auch μ-rekursiv. ▲
NEA ☞ Abschnitt 5.3	Nichtdeterministischer endlicher ☞ Akzeptor. Im Gegensatz zu seinem deterministischen Pendant ( ☞ DEA) können für die gleiche Eingabe mehrere mögliche Zustandsübergänge definiert sein und damit mehrere verschiedene Berechnungsfolgen für die gleiche Eingabe existieren. Mit dem ☞ Potenzmengenautomaten existiert zu jedem NEA ein DEA, der die gleiche ☞ formale Sprache akzeptiert. Die von DEAs und NEAs akzeptierten Sprachklassen sind identisch und entsprichen der Klasse der ☞ regulären Sprachen. ▲
Negationsnormalform ☞ Abschnitt 3.2.2	Eine Formel liegt in Negationsnormalform vor, wenn das Negationszeichen nur vor atomaren Formeln auftaucht. In der ☞ Prädikatenlogik wird diese Darstellung als Zwischenschritt in der Erzeugung der ☞ Pränex-Form verwendet. ▲
NEXP ☞ Abschnitt 7.2.3	Die ☞ Komplexitätsklasse NEXP enthält alle Sprachen, die von nichtdeterministischen ☞ Turing-Maschinen in exponentieller Zeit entschieden werden können. ▲
NP ☞ Abschnitt 7.2.1	Die ☞ Komplexitätsklasse NP enthält alle Sprachen, die von nichtdeterministischen ☞ Turing-Maschinen in polynomieller Zeit entschieden werden können. NP ist eine Obermenge von ☞ P. Ob es sich dabei um eine echte Obermenge handelt (NP\P≠ ∅), ist Gegenstand des derzeit ungelösten ☞ P-NP-Problems. ▲
NP-hart ☞ Abschnitt 7.3.2	Ein Problem ist NP-hart, wenn sich sämtliche Probleme der Komplexitätsklasse ☞ NP durch ☞ polynomielle Reduktion darauf abbilden lassen. Ein NP-hartes Problem kann, muss aber nicht selbst in der Klasse NP liegen. ▲
NPSPACE ☞ Abschnitt 7.2.2	Die ☞ Komplexitätsklasse NPSPACE enthält alle Sprachen, die von nichtdeterministischen ☞ Turing-Maschinen mit polynomiellem Bandplatzverbrauch entschieden werden können. Aus dem ☞ Satz von Savitch folgt, dass die Klasse NSPACE mit der Klasse ☞ PSPACE übereinstimmt. ▲
NP-vollständig ☞ Abschnitt 7.3.2	Ein Problem ist NP-vollständig, wenn es ☞ NP-hart ist und selbst in der Klasse ☞ NP liegt. NP-vollständige Probleme gelten als die schwierigsten Probleme innerhalb von NP, da sich alle anderen Probleme durch ☞ polynomielle Reduktion darauf abbilden lassen. ▲
O-Notation ☞ Abschnitt 7.1.1	Standardschreibweise für die Benennung von ☞ Komplexitätsklassen. Das große ’O’ ist eines von fünf ☞ Landau-Symbolen und der Namensgeber dieser Notation. ▲
P ☞ Abschnitt 7.2.1	Die ☞ Komplexitätsklasse P enthält alle Sprachen, die von deterministischen ☞ Turing-Maschinen in polynomieller Zeit entschieden werden können. P ist eine Teilmenge von ☞ NP. Ob es sich dabei um eine echte Teilmenge handelt (NP\P≠ ∅), ist Gegenstand des derzeit ungelösten ☞ P-NP-Problems. ▲
Paarungsfunktion ☞ Abschnitt 2.3.3	Die Cantor’sche Paarungsfunktion bildet die Elemente der Menge ℕ × ℕ bijektiv auf die Menge ℕ ab. Ihre Existenz beweist, dass die Menge ℕ k für alle k ∈ ℕ die gleiche ☞ Mächtigkeit besitzt wie die natürlichen Zahlen selbst. ▲
Parikh-Vektor ☞ Abschnitt 5.7	Vektordarstellung einer Sequenz von nacheinander schaltenden Transitionen eines ☞ Petri-Netzes. Durch die Multiplikation mit der ☞ Inzidenzmatrix lässt sich die Folgekonfiguration eines Petri-Netzes berechnen. ▲
Partielle Funktion ☞ Abschnitt 2.2	Funktion, die nicht für alle Elemente ihres Definitionsbereichs einen definierten Funktionswert besitzt. In der klassischen Mathematik ist dieser Begriff unbekannt – dort sind alle Funktionen per Definition ☞ total. In der theoretischen Informatik werden partielle Funktionen für die Beschreibung von Algorithmen eingesetzt, die für gewisse Eingabewerte nicht terminieren. ▲
Peano-Axiome ☞ Abschnitt 2.3.1	Formale Beschreibung der natürlichen Zahlen, die aus insgesamt fünf Axiomen besteht. Die Peano-Axiome dienen uns heute als Grundlage für den berechenbarkeitstheoretischen Umgang mit den natürlichen Zahlen. Unter anderem folgt aus Peanos fünftem Axiom, dem ☞ Induktionsaxiom, dass die ☞ Prädikatenlogik erster Stufe zu schwach ist, um die natürlichen Zahlen zu formalisieren. ▲
Petri-Netz ☞ Abschnitt 5.7	Formales Modell zur Beschreibung nebenläufiger Systeme. Genau wie ☞ endliche Automaten arbeiten Petri-Netze zustandsbasiert, verfügen jedoch über deutlich komplexere Übergangsmechanismen. Streng unterschieden werden Bedingungen und Ereignisse. Erstere werden durch Stellen, letztere durch Transitionen beschrieben. In einem Petri-Netz wird der aktuelle Zustand eines Systems durch Marken modelliert. Schaltet eine Transition, so wird eine Marke aus jeder Eingabestelle entfernt und jeder Ausgangsstelle eine zusätzliche Marke hinzugefügt. ▲
P-NP-Problem ☞ Abschnitt 7.3.2	Hinter diesem Problem verbirgt sich die Frage, ob jede Sprache, die durch eine nichtdeterministische Turing-Maschine in polynomieller Zeit entschieden werden kann, auch von einer deterministischen Turing-Maschine in polynomieller Zeit entschieden werden kann. Das P-NP-Problem gilt als das wichtigste der bis dato offenen Probleme der theoretischen Informatik, da seine Lösung weitreichende Konsequenzen für nahezu alle Teilbereiche der Informatik hat. Wäre P = NP, so ließen sich viele Algorithmen in polynomieller Zeit lösen, für die heute ausschließlich Algorithmen mit exponentiellem Zeitaufwand existieren. Unter anderem wären viele kryptografische Systeme auf einen Schlag angreifbar. In der großen Zahl der bisher entdeckten ☞ NP-vollständigen Probleme sehen viele Experten einen Hinweis darauf, dass P und NP voneinander verschieden sind. Einen formalen Beweis für diese Vermutung konnte jedoch noch niemand erbringen. ▲
Polynomielle Reduktion ☞ Abschnitt 7.3.1	Wichtiges Beweisprinzip der ☞ Komplexitätstheorie. Im Rahmen eines Reduktionsbeweises wird gezeigt, dass sich ein Problem lösen lässt, indem die Fragestellung in polynomieller Zeit auf ein anderes Problem abgebildet wird, dessen (polynomielle) Lösung bereits bekannt ist. Durch den geschickten Einsatz dieser Technik lassen sich die Komplexitätseigenschaften vieler Probleme auf weitere Fragestellungen übertragen. Der Begriff ist eng verwandt mit der ☞ Reduzierbarkeit aus dem Bereich der ☞ Berechenbarkeitstheorie. ▲
Post’sches Korrespondenzproblem ☞ Abschnitt 6.5.4	Für eine Folge von Wortpaaren ( x 1 ,y 1 ) , ( x 2 ,y 2 ) , … , ( x n ,y n ) gilt es zu entscheiden, ob eine Indexsequenz i 1 , … ,i k existiert, so dass die Konkatenation von x i 1 , … ,x i k die gleiche Zeichenkette hervorbringt wie die Konkatenation von y i 1 , … ,y i k . Genau wie das ☞ Halteproblem ist auch das ☞ Post’sche Korrespondenzproblem ☞ unentscheidbar. Die Eigenschaft, auf viele andere Problemstellungen ☞ reduzierbar zu sein, macht das Post’sche Korrespondenzproblem zu einem der wichtigsten Hilfsmittel im Bereich der ☞ Berechenbarkeitstheorie. ▲
Potenzmengenautomat ☞ Abschnitt 5.3.2	Spezieller Automat, der die Potenzmenge der Zustände eines anderen Automaten als Zustandsraum verwendet. Der Potenzmengenautomat ist der Schlüssel, um die Äquivalenz von ☞ DEAs und ☞ NEAs zu beweisen. Die Konstruktion ermöglicht es, jeden ☞ NEA in einen ☞ DEA zu übersetzen, der die gleiche Sprache akzeptiert. ▲
Prädikatenlogik ☞ Abschnitt 3.2	Die Prädikatenlogik erweitert die ☞ Aussagenlogik um mehrstellige Prädikate sowie um die Quantoren ∀ („für alle“) und ∃ („es existiert“). Viele Aspekte des logischen Schließens, die in der Aussagenlogik nicht ausgedrückt werden können, lassen sich mit Hilfe prädikatenlogischer Formeln formal beschreiben. Die Prädikatenlogik ist die Grundlage der Programmiersprache ☞ Prolog. ▲
Pränex-Form ☞ Abschnitt 3.2.2	Eine Formel liegt in Pränex-Form vor, wenn alle Quantoren links von den anderen Formelbestandteilen stehen. Ausgehend von der ☞ Negationsnormalform lässt sich jede Formel der ☞ Prädikatenlogik in eine äquivalente Formel in Pränex-Form übersetzen. ▲
Primitive Rekursion ☞ Abschnitt 6.1.4	Eine Funktion f : ℕ 0 2 → ℕ 0 ist nach dem Schema der primitiven Rekursion aufgebaut, wenn sie die folgende Form besitzt: ▲ f ( m,n ) = ▲
Primitiv-rekursive Funktion ☞ Abschnitt 6.1.4	Kleinste Menge von Funktionen, die die Nullfunktion, die Nachfolgerfunktion und die Projektion enthält und bez. Komposition und ☞ primitiver Rekursion abgeschlossen ist. Die Klasse der primitiv-rekursiven Funktionen besitzt die gleiche Berechnungsstärke wie die ☞ Loop-Sprache. Mit anderen Worten: Jede primitiv-rekursive Funktion lässt sich mit einem Loop-Programm berechnen und jede Loop-berechenbare Funktion ist ihrerseits primitiv-rekursiv. Die primitiv-rekursiven Funktionen sind vollständig in der Menge der ☞ μ-rekursiven Funktionen enthalten. ▲
Prolog ☞ Abschnitt 3.2.4	Logische Programmiersprache, die auf dem prädikatenlogischen ☞ Resolutionskalkül basiert. Prolog-Programme bestehen aus einer Problembeschreibung in Form von Logikformeln. Wird eine Anfrage gestellt, versucht der Prolog-Interpreter, die Antwort selbstständig aus der Problembeschreibung zu deduzieren. ▲
PSPACE ☞ Abschnitt 7.2.2	Die ☞ Komplexitätsklasse PSPACE enthält alle Sprachen, die von deterministischen ☞ Turing-Maschinen mit polynomiellem Bandplatzverbrauch entschieden werden können. Aus dem ☞ Satz von Savitch folgt, dass die Klasse PSPACE mit der Klasse ☞ NPSPACE übereinstimmt. ▲
Pumping-Lemma ☞ Abschnitt 4.3.2	Hilfsmittel, um zu beweisen, dass eine Menge L ⊆ Σ * keine ☞ reguläre Sprache oder keine ☞ kontextfreie Sprache ist. Das Pumping-Lemma nutzt die Eigenschaft dieser Sprachklassen aus, dass mit jedem hinreichend langen Wort ω ∈ L auch diejenigen Wörter ω i in L enthalten sind, die durch das Duplizieren gewisser Teilsequenzen entstehen. ▲
Rechtsableitung ☞ Abschnitt 4.1	Ableitungssequenz mit der Eigenschaft, dass in jedem Schritt das am weitesten rechts stehende Nonterminal ersetzt wurde. ▲
Reduktion ☞ Abschnitt 6.5	Wichtiges Beweisprinzip der ☞ Berechenbarkeitstheorie. Im Rahmen eines Reduktionsbeweises wird gezeigt, dass sich ein Problem lösen lässt, indem die Fragestellung auf ein anderes Problem abgebildet wird, dessen Lösung bereits bekannt ist. Durch den geschickten Einsatz dieser Technik lassen sich die Berechenbarkeitseigenschaften vieler Probleme auf weitere Fragestellungen übertragen. Der Begriff ist eng verwandt mit der ☞ polynomiellen Reduzierbarkeit aus dem Bereich der ☞ Komplexitätstheorie. ▲
Registermaschine ☞ Abschnitt 6.1.6.1	Spezielles ☞ Berechnungsmodell, das der Architektur realer Computersysteme sehr nahe kommt. Eine Registermaschine setzt sich aus dem Eingabeband, dem Ausgabeband und der Zentraleinheit zusammen. Letztere besteht aus dem Speicher, dem Programm und zwei Registern. Die Programmanweisungen werden über den Befehlszähler adressiert und sequentiell abgearbeitet. Arithmetische Berechnungen werden im Akkumulator durchgeführt. Die Registermaschine besitzt die gleiche Berechnungsstärke wie die ☞ While-Sprache, die ☞ Goto-Sprache, die ☞ Turing-Maschine und die ☞ μ-rekursiven Funktionen. Nach der ☞ Church’schen These lässt sich jede intuitiv berechenbare Funktion mit Hilfe einer ☞ Registermaschine berechnen. ▲
Regulärer Ausdruck ☞ Abschnitt 4.3.3	Alternative Beschreibungsform für ☞ reguläre Sprachen. Reguläre Ausdrücke sind der De-facto-Standard für die Spezifikation von Suchmustern. ▲
Reguläre Grammatik ☞ Abschnitt 4.2	☞ Kontextfreie Grammatik mit der zusätzlichen Eigenschaft, dass die rechte Seite einer Produktion entweder aus dem leeren Wort ϵ oder einem Terminalsymbol, gefolgt von einem Nonterminal, besteht. In der Nomenklatur der ☞ Chomsky-Hierarchie werden kontextfreie Grammatiken als Typ-3-Grammatiken bezeichnet. ▲
Reguläre Sprache ☞ Abschnitt 4.2	Eine Sprache L heißt regulär, falls eine ☞ reguläre Grammatik existiert, die L erzeugt. Die Menge der regulären Sprachen stimmt mit der Menge der von ☞ DEAs und ☞ NEAs akzeptierten Sprachen überein. ▲
Resolutionskalkül ☞ Abschnitt 3.1.3	Spezielles ☞ Widerspruchskalkül der ☞ Aussagenlogik und ☞ Prädikatenlogik. Um die ☞ Allgemeingültigkeit einer Formel F zu zeigen, wird die negierte Formel ¬ F in eine Menge von ☞ Klauseln übersetzt. Anschließend werden in einem iterativen Prozess neue Resolventen abgeleitet. Wird die leere Klausel □ deduziert, so terminiert das Verfahren. In diesem Fall ist gezeigt, dass ¬ F kein ☞ Modell besitzt und F demnach eine ☞ Tautologie sein muss. ▲
Robinson-Algorithmus ☞ Abschnitt 3.2.3.1	Systematisches Verfahren, um eine Menge prädikatenlogischer Formeln zu ☞ unifizieren. Der Algorithmus durchsucht die Formeln zeichenweise von links nach rechts. Abweichungen werden durch Substitutionen korrigiert. Sind die Eingabeformeln unifizierbar, so lässt sich der Unifikator durch die Verkettung der berechneten Substitutionen erzeugen. Der Algorithmus von Robinson berechnet den ☞ allgemeinsten Unifikator der Eingabemenge. ▲
Rucksackproblem ☞ Abschnitt 7.1	Ein Rucksack ist so mit Gegenständen zu bepacken, dass der erzielte Gesamtwert maximal wird, ohne das Fassungsvermögen zu überschreiten. In der hier vorgestellten Variante sind für jeden Gegenstandstyp beliebig viele Exemplare vorhanden und die Werte und Volumina ganzzahlig. Unter diesen Voraussetzungen lässt sich das Rucksackproblem effizient mit dem Mittel der ☞ dynamischen Programmierung lösen. Eine leichte Abwandlung der Problemstellung lässt dagegen ein ☞ NP-vollständiges Problem entstehen. ▲
Russell’sche Antinomie ☞ Abschnitt 1.2.1	Fundamentaler Widerspruch in der Cantor’schen Mengenlehre. Unter der Annahme, dass sich eine Menge M entweder selbst enthält oder nicht selbst enthält, definierte der britische Mathematiker Bertrand Russell die Menge aller Menge, die sich nicht selbst als Element enthalten. Genau wie im Falle des ☞ Barbier-Paradoxons führt diese Definition einen fundamentalen Widerspruch herbei. Erst der formale axiomatische Aufbau der Mengenlehre durch Ernst Zermelo und Abraham Fraenkel konnte die entdeckte Inkonsistenz im Cantor’schen Begriffsgerüst entgültig beheben. ▲
SAT ☞ Abschnitt 7.3.3	Frage nach der ☞ Erfüllbarkeit einer Formel der ☞ Aussagenlogik. Zu den Sternstunden der theoretischen Informatik gehört der Beweis, dass SAT ein ☞ NP-vollständiges Problem ist ( ☞ Satz von Cook). ▲
Satz von Cantor ☞ Abschnitt 2.3.3	Gleich mehrere zentrale Ergebnisse der Mathematik werden mit Georg Cantors Namen verbunden. Hierzu gehört der Nachweis, dass ℕ und ℕ 2 die gleiche ☞ Mächtigkeit besitzen (zu zeigen über das erste Cantor’sche Diagonalisierungsargument), wie auch der Satz über die ☞ Überabzählbarkeit der reellen Zahlen (zu zeigen über das zweite Cantor’sche Diagonalisierungsargument). ▲
Satz von Cook ☞ Abschnitt 7.3.3	Im Jahre 1971 gelang es Stephen Cook, die ☞ NP-Vollständigkeit von ☞ SAT zu beweisen, ohne auf das Prinzip der ☞ polynomiellen Reduktion zurückzugreifen. Der Satz ist in zweierlei Hinsicht von Bedeutung. Zum einen beweist er, dass NP-vollständige Probleme wirklich existieren. Zum anderen lassen sich durch polynomielle Reduktion andere Fragestellungen als NP-vollständig identifizieren. Hierzu gehören unter anderem das ☞ Hamilton-Problem sowie die Probleme CLIQUE, SELECT, PARTITION, BIN PACKING und TRAVELING SALESMAN. Für die Durchführung der Reduktion wird zumeist auf die vereinfachte Variante ☞ 3SAT zurückgegriffen, die ebenfalls NP-vollständig ist. ▲
Satz von Herbrand ☞ Abschnitt 3.2.3	Der Satz von Herbrand stellt einen wichtigen Zusammenhang zwischen der ☞ Prädikatenlogik und der ☞ Aussagenlogik her. Er besagt, dass eine Formel F in ☞ Skolem-Form genau dann ein ☞ Herbrand-Modell besitzt, wenn alle endlichen Teilmengen der ☞ Grundinstanzen von F im aussagenlogischen Sinne erfüllbar sind. ▲
Satz von Kleene ☞ Abschnitt 6.1.2	Besagt, dass sich jede While-berechenbare Funktion mit einem ☞ While-Programm berechnen lässt, das eine einzige Schleife besitzt. Die Anzahl der Schleifen, die für die Umsetzung eines Algorithmus benötigt werden, ist somit unabhängig von dessen Komplexität. ▲
Satz von Rabin und Scott ☞ Abschnitt 5.3.2	Besagt, dass zu jedem nichtdeterministischen endlichen Automaten ein deterministischer endlicher Automat existiert, der die gleiche Sprache akzeptiert. ▲
Satz von Rice ☞ Abschnitt 6.5.2	Im Jahre 1953 gelang es Henry Gordon Rice, einen Zusammenhang zwischen dem ☞ Halteproblem und einer beliebigen nichttrivialen Eigenschaft von Turing-Maschinen herzustellen. Aus dem Satz von Rice folgt unmittelbar, dass es unmöglich ist, irgendeine nichttriviale Eigenschaft von Turing-Maschinen algorithmisch zu überprüfen. ▲
Satz von Savitch ☞ Abschnitt 7.2.2	Besagt, dass jedes von einer nichtdeterministischen ☞ Turing-Maschine lösbare Problem mit einer deterministischen Turing-Maschine gelöst werden kann, deren Platzbedarf nur quadratisch höher liegt. ▲
Schlussregel ☞ Abschnitt 3.1.3.1	Zentraler Bestandteil eines ☞ Hilbert-Kalküls. Die Schlussregeln eines Kalküls definieren, wie sich aus bestehenden Aussagen neue Aussagen ableiten lassen. In einem formalen Beweis wird die zu zeigende Behauptung durch die sukzessive Anwendung der Schlussregeln aus den ☞ Axiomen deduziert. ▲
Semantik ☞ Abschnitt 3.1.1	Während die ☞ Syntax den strukturellen Aufbau von Objekten beschreibt, befasst sich die Semantik mit deren Bedeutung. Im Bereich der natürlichen Sprache definiert die Semantik, welche Elemente der realen Welt sich hinter den gesprochenen Wörtern verbergen. ▲
Semi-Entscheidbarkeit ☞ Abschnitt 6.4	Eine Menge M heißt semi-entscheidbar, falls die partielle ☞ charakteristische Funktion ☞ berechenbar ist. Für eine semi-entscheidbare Menge M ⊆ Σ * existiert ein systematisches Verfahren, das für alle Elemente ω ∈ M nach endlicher Zeit die Mengenzugehörigkeit bestätigt. Ist ω ⁄∈ M, so kommt die Berechnung zu keinem Ende. ▲
Skolem-Form ☞ Abschnitt 3.2.2	Eine prädikatenlogische Formel liegt in Skolem-Form vor, wenn sie die ☞ Pränex-Form besitzt und keine Existenzquantoren mehr enthält. Jede Formel der ☞ Prädikatenlogik lässt sich in eine ☞ erfüllbarkeitsäquivalente Formel in Skolem-Form übersetzen. ▲
Spezielles Halteproblem ☞ Abschnitt 6.5	Synonym für die Frage, ob für jede ☞ Turing-Maschine T algorithmisch entschieden werden kann, ob T unter Eingabe der eigenen Gödelnummer ⟨ T ⟩ terminiert ( ☞ Gödelisierung). Das spezielle Halteproblem ist ☞ unentscheidbar. ▲
Strukturelle Induktion ☞ Abschnitt 2.4.2	Variante der ☞ vollständigen Induktion, mit der sich Aussagen über rekursiv definierte Strukturen beweisen lassen. Hierzu wird die Aussage zunächst für alle Basisfälle explizit bewiesen und anschließend gezeigt, dass sich deren Gültigkeit auf zusammengesetzte Objekte vererbt. ▲
Syntax ☞ Abschnitt 3.1.1	Die Syntax befasst sich mit dem strukturellen Aufbau von Objekten. Im Bereich der natürlichen Sprache definiert die Syntax die Regeln, nach denen einzelne Wörter zu grammatikalisch korrekten Sätzen kombiniert werden können. Auf der syntaktischen Ebene werden Objekte als sinnleere Symbolketten verstanden. Erst die ☞ Semantik weißt den einzelnen Objekten eine Bedeutung zu. ▲
Syntaxbaum ☞ Abschnitt 4.1	Baumförmige Darstellung der Ableitungssequenzen einer ☞ Grammatik. Ein Syntaxbaum wird so konstruiert, dass alle inneren Knoten mit Nonterminalen und alle Blätter mit Terminalsymbolen markiert sind. In der Baumdarstellung geht die Information über die Reihenfolge der Produktionsanwendungen verloren, so dass verschiedene Ableitungssequenzen zu demselben Syntaxbaum führen können. ▲
Tableaukalkül ☞ Abschnitt 3.1.3.3	Spezielles ☞ Widerspruchskalkül der ☞ Aussagenlogik und ☞ Prädikatenlogik. Um die ☞ Allgemeingültigkeit einer Formel F zu zeigen, wird aus den Teilformeln von ¬ F eine Baumstruktur – das sogenannte Tableau – erzeugt. Anhand spezieller Abschlussbedingungen lassen sich offene und geschlossene Zweige identifizieren. Sind alle Zweige geschlossen, so besitzt ¬ F kein Modell und F ist als Tautologie identifiziert. ▲
Tautologie ☞ Abschnitt 3.1.1	Bezeichnung für eine uneingeschränkt wahre Aussage. Der Begriff wird synonym mit dem Begriff der ☞ Allgemeingültigkeit verwendet. ▲
Theoretische Informatik ☞ Kapitel 1 – 7	Untersucht die mathematischen Methoden und Modelle, die sich hinter der Fassade der modernen Hardware- und Software-Technik verbergen. Wichtige Teilbereiche der theoretischen Informatik sind die ☞ Logik, die Theorie der ☞ formalen Sprachen, die Theorie der ☞ endlichen Automaten sowie die ☞ Berechenbarkeits- und die ☞ Komplexitätstheorie. ▲
Totale Funktion ☞ Abschnitt 2.2	Funktion, die für alle Elemente ihres Definitionsbereichs einen festgelegten Funktionswert besitzt. In der klassischen Mathematik sind alle Funktionen per Definition total und daher nicht explizit als solche gekennzeichnet. In der theoretischen Informatik existiert zusätzlich der Begriff der ☞ partiellen Funktion. ▲
Transduktor ☞ Abschnitt 5.6	Neben den ☞ Akzeptoren die zweite große Untergruppe ☞ endlicher Automaten. Transduktoren bestehen aus einer Menge von Zuständen, einem Eingabe- und einem Ausgabealphabet, einer Zustandsübergangsfunktion sowie einem dedizierten Startzustand. In jedem Verarbeitungsschritt nimmt der Automat ein einzelnes Eingabezeichen entgegen und übersetzt dieses in ein Ausgabezeichen. Die Verarbeitung endet, wenn das letzte Eingabezeichen eingelesen wurde. Die Übersetzung von Transduktoren in digitale Hardware-Schaltungen ist Gegenstand der ☞ Automatensynthese. ▲
Turing-Berechenbarkeit ☞ Abschnitt 6.1.5	Eine Funktion f heißt Turing-berechenbar, falls eine ☞ Turing-Maschine existiert, die f berechnet. Nach der ☞ Church’schen These ist die Klasse der Turing-berechenbaren Funktionen mit der Klasse der intuitiv berechenbaren Funktionen identisch. ▲
Turing-Maschine ☞ Abschnitt 6.1.5	Mathematisches Modell, um den Berechenbarkeitsbegriff formal zu erfassen. Grundlage ist ein eindimensionales Band, das sich aus unendlich vielen, nebeneinander angeordneten Zellen zusammensetzt. Die Maschine verfügt über einen Schreib-Lese-Kopf, der zu jeder Zeit über einer bestimmten Zelle positioniert ist. In jedem Bearbeitungsschritt kann eine Turing-Maschine das aktuell betrachtete Symbol durch ein anderes ersetzen und den Schreib-Lese-Kopf verschieben. Die ausgeführten Aktionen gehen mit einem potenziellen Wechsel des inneren Zustands einher. Anders als z. B. im Falle des ☞ Transduktors werden alle Lese- und alle Schreiboperationen auf dem gleichen Band ausgeführt. Turings Maschinenmodell besitzt die gleiche Berechnungsstärke wie die ☞ While-Sprache, die ☞ Goto-Sprache, die ☞ Registermaschine und die ☞ μ-rekursiven Funktionen. Nach der ☞ Church’schen These lässt sich jede intuitiv berechenbare Funktion mit Hilfe eine Turing-Maschine berechnen. ▲
Überabzählbarkeit ☞ Abschnitt 2.3.3	Eine Menge M mit unendlich vielen Elementen heißt überabzählbar, wenn es nicht möglich ist, M bijektiv auf die Menge der natürlichen Zahlen abzubilden. Mit dem Mittel der ☞ Diagonalisierung kann unter anderem die Überabzählbarkeit der reellen Zahlen gezeigt werden. Der Begriff ist eng verwandt mit dem Begriff der ☞ Abzählbarkeit. ▲
Unberechenbarkeit ☞ Abschnitt 6.1	Eine Funktion f heiß unberechenbar, falls kein systematisches Verfahren existiert, das für alle Eingaben x nach endlich vielen Schritten terminiert und den Funktionswert f ( x ) als Ausgabe liefert. Was wir unter einem systematischen Verfahren zu verstehen haben, wird durch die Definition eines ☞ Berechnungsmodells formal festgelegt. Der Begriff der unberechenbaren Funktion ist eng mit dem Begriff der ☞ Unentscheidbarkeit gekoppelt. ▲
Unentscheidbarkeit ☞ Abschnitt 6.4	Eine Menge M heißt unentscheidbar, falls die ☞ charakteristische Funktion ☞ unberechenbar ist. Für eine unentscheidbare Menge M existiert kein systematisches Verfahren, das für alle Eingaben ω nach endlicher Zeit beantwortet, ob ω ein Element von M ist oder nicht. Viele praktische Fragestellungen, zu denen auch das ☞ Halteproblem und das ☞ Post’sche Korrespondenzproblem gehören, wurden in der Vergangenheit als unentscheidbar identifiziert. ▲
Unerfüllbarkeit ☞ Abschnitt 3.1.1	Eine unerfüllbare Formel besitzt die Eigenschaft, kein einziges ☞ Modell zu besitzen. Eine solche Formel ist damit immer falsch, unabhängig davon, wie wir ihre Bestandteile interpretieren. ▲
Unifikation ☞ Abschnitt 3.2.3.1	Methode, die für eine Menge prädikatenlogischer Formeln einen ☞ Unifikator berechnet. Ein bekannter Vertreter ist der ☞ Robinson-Algorithmus zur Berechnung des ☞ allgemeinsten Unifikators. ▲
Unifikator ☞ Abschnitt 3.2.3.1	Eine Menge prädikatenlogischer Formeln { F 1 , … ,F n } heißt unifizierbar, falls eine Substitution σ existiert mit σF 1 = … = σF n . Die Substitution σ wird als Unifikator bezeichnet. ▲
Universelle Turing-Maschine ☞ Abschnitt 6.1.5	Spezielle Turing-Maschine, die in der Lage ist, jede andere Turing-Maschine zu simulieren. Hierzu wird die zu simulierende Maschine ☞ gödelisiert und zusammen mit dem Eingabewort auf das Band geschrieben. ▲
Up-Arrow-Notation ☞ Abschnitt 2.3.2	Von Donald E. Knuth eingeführte Schreibweise, mit der sich arithmetische Verknüpfungen in einem einheitlichen Schema darstellen lassen. Unter anderem ermöglicht die ↑-Notation, Operatoren wie die Hyperpotenz aufzuschreiben, für die in der klassischen Mathematik kein natives Symbol existiert. ▲
Vollständige Induktion ☞ Abschnitt 2.4.1	Neben dem direkten und dem indirekten Beweis ist die vollständige Induktion die dritte klassische Beweistechnik der Mathematik. Sie ist immer dann anwendbar, wenn eine parametrisierte Aussage A ( n ) für alle natürlichen Zahlen n bewiesen werden soll. Ein Induktionsbeweis erfolgt in drei Schritten: Zunächst wird im Induktionsanfang die Aussage für einen oder mehrere Basisfälle bewiesen. Im nächsten Schritt erfolgt die Annahme, dass die Aussage für ein gewisses n und alle kleineren Werte bewiesen sei (Induktionsannahme). Gelingt im Anschluss der Beweis, dass aus der Gültigkeit von A ( n ) die Gültigkeit von A ( n +1) folgt, so ist die Aussage für alle n bewiesen. Eine mit der vollständigen Induktion verwandte Beweistechnik ist die ☞ strukturelle Induktion. ▲
While-Programm ☞ Abschnitt 6.1.2	Programm, verfasst in der fiktiven ☞ While-Sprache. Die While-Schleife ist die einzige Möglichkeit, den Kontrollfluss zu steuern. Nach der ☞ Church’schen These lässt sich jede intuitiv berechenbare Funktion mit Hilfe eines While-Programms berechnen. ▲
While-Sprache ☞ Abschnitt 6.1.2	Menge aller ☞ While-Programme. Nach der ☞ Church’schen These sind alle intuitiv berechenbaren Funktionen f While-berechenbar, d. h., es existiert ein While-Programm, das x als Eingabe entgegennimmt und f ( x ) als Ausgabe liefert. Die While-Sprache besitzt die gleiche Berechnungsstärke, wie die ☞ Goto-Sprache, die ☞ Turing-Maschine, die ☞ Registermaschine und die ☞ μ-rekursiven Funktionen. ▲
Widerspruchskalkül ☞ Abschnitt 3.1.3	Spezieller ☞ Kalkül, der die ☞ Allgemeingültigkeit einer Formel über die ☞ Unerfüllbarkeit der negierten Aussage beweist. Bekannte Vertreter sind der ☞ Resolutionskalkül und der ☞ Tableaukalkül. ▲
Wortproblem ☞ Abschnitt 4.1	Wichtige Problemstellung aus dem Bereich der ☞formalen Sprachen. Hinter dem Wortproblem verbirgt sich die Frage, ob ein bestimmtes Wort ω in einer Sprache L enthalten ist. Mit anderen Worten: Gilt ω ∈ L? ▲
Zellulärer Automat ☞ Abschnitt 5.8	Zustandsbasiertes System, das aus einer großen Anzahl simultan arbeitender Elementarautomaten, den sogenannten Zellen, besteht. Zu jedem Zeitpunkt befinden sich diese in einem von endlich vielen Zuständen. In jedem Schaltschritt geht eine Zellen in eine Folgekonfiguration über, die sowohl durch ihren eigenen Zustand als auch durch die Zustände ihrer Nachbarn bestimmen wird. Hierdurch stehen die Zellen in ständiger Interaktion. Eingesetzt wird das Modell vor allem zur Beschreibung dynamischer, selbstorganisierender Systeme.   ▲