Termalgebra

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Herbrand-Struktur)
Wechseln zu: Navigation, Suche

Eine Termalgebra ist eine algebraische Struktur, die aus einer algebraischen Signatur frei generiert wird. Die Signatur gibt die Operationen der Algebra an mit deren Stelligkeiten – inklusive nullstellige Operationen, auch Konstanten genannt.

Zum Beispiel sind freie Halbgruppen isomorph zu Termalgebren, die aus einer Signatur generiert werden, die nur aus einer Binäroperation besteht (der Multiplikation-Operation der Halbgruppe) und einer Menge an Konstanten.

Termalgebren sind wichtig bei der Bestimmung der Bedeutung (Semantik) von abstrakten Datentypen (ADTs). Hierbei bietet die ADT-Deklaration einer Signatur für eine algebraische Struktur mit mehreren Typen. Die Termalgebra ist ein konkretes Modell der abstrakten Deklaration.

Eine Struktur \mathfrak{A} =\left(A,(f_i)_{i\in I},(R_j)_{j\in J}\right), für die die algebraische Struktur \mathfrak{A}_{\mathrm{alg}} = \left(A, (f_i)_{i \in I}\right) eine Termalgebra ist, wird als Herbrand-Struktur bezeichnet. Herbrand-Strukturen spielen in der Logik, insbesondere in der logischen Programmierung eine Rolle. Eine Herbrand-Interpretation ordnet einer (nicht notwendig algebraischen) Signatur eine Herbrand-Struktur zu.

Die Termalgebra zu einer algebraischen Signatur ist das Initialobjekt in der Kategorie aller Strukturen dieser Signatur.

Herbrand-Strukturen werden im Satz von Herbrand verwendet und sind nach Jacques Herbrand benannt.

Entscheidbarkeitsfragen[Bearbeiten]

Termalgebren sind entscheidbar unter der Eliminierung von Quantifizierern. Die Komplexität des Entscheidungsproblems gehört zur Klasse NONELEMENTARY.

Literatur[Bearbeiten]

  • Anatolii Ivanovic Mal'cev: "The Metamathematics of Algebraic Systems". North-Holland, 1971. (Studies in Logic and The Foundations of Mathematics, Volume 66)
  • H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag 1996, ISBN 3-8274-0130-5