Equational specifications, complete term rewriting systems, and computable and semicomputable algebras
Jan Aldert Bergstra, John Vivian Tucker · Journal of the ACM · 1995
We classify the computable and semicomputable algebras in terms of finite equational initial algebra specifications and their properties as term term rewriting systems, such as completeness.Further results on properties of these specifications, such as on their size and orthogonality, are provided which show that our main results are the best possible.