Term algebra
From Wikipedia, the free encyclopedia
In universal algebra, a term algebra is an algebraic structure which is freely generated from a signature specifying the operations of the algebra (including constants, which are nullary operations). For example, free magmas are isomorphic to term algebras generated from a signature consisting of one binary operation (the multiplication operation of the magma) plus a set of constants.
Term algebras play a role in the semantics of abstract data types, where an abstract data type declaration provides the signature of a multi-sorted algebraic structure and the term algebra is a concrete model of the abstract declaration.
[edit] Decidability of term algebras
Term algebras can be shown decidable using quantifier elimination. The complexity of the decision problem is NONELEMENTARY.
[edit] See also
[edit] References
- Anatolii Ivanovic Mal'cev: "The Metamathematics of Algebraic Systems". North-Holland, 1971. (Studies in Logic and The Foundations of Mathematics, Volume 66)
