Termalgebra
aus Wikipedia, der freien Enzyklopädie
Eine Termalgebra ist eine Algebraische Struktur, die aus einer 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 eine 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 ein algebraische Struktur mit mehreren Typen. Die Termalgebra ist ein konkretes Modell der abstrakten Deklaration.
[Bearbeiten] Entscheidbarkeitsfragen
Termalgebren sind entscheidbar unter der Eliminierung von Quantifizierern. Der Komplexität des Entscheidungsproblems gehört zur Klasse NONELEMENTARY.
[Bearbeiten] Literatur
- Anatolii Ivanovic Mal'cev: "The Metamathematics of Algebraic Systems". North-Holland, 1971. (Studies in Logic and The Foundations of Mathematics, Volume 66)