Algebras of iteration theories

摘要

The equational class generated by rational algebraic theories was characterized in Esik, Comput. Linguistics and Comput. Languages XIV (1980), 183–207. Here, this class will be called the class of iteration theories. Also, there is a close connection between Elgot's iterative theories and iteration theories. In this paper we introduce algebras for iteration theories, called iteration algebras. Iteration algebras are natural generalization of regular algebras and they are closely related to iterative algebras as well. It is shown that the absolutely free iteration algebras are the algebras of regular trees.