Termalgebra

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.

Entscheidbarkeitsfragen

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

Literatur

• Anatolii Ivanovic Mal'cev: "The Metamathematics of Algebraic Systems". North-Holland, 1971. (Studies in Logic and The Foundations of Mathematics, Volume 66)