n -Rational Algebras I. Basic Properties and Free Algebras
Jean H. Gallier · SIAM Journal on Computing · 1984
A (strict) hierarchy of algebras in which only certain “constructive” chains have a least upper bound is studied. Such algebras, called n-rational, are “ideal” interpretations for finite recursion schemes of higher types. Indeed, the constructive chains that have least upper bounds in these algebras are obtained by unfolding rational recursion schemes of higher types. Part I of this paper deals with basic properties of these algebras, the existence of free algebras in particular. In Part II [SIAM J. Comput., 13 (1984), pp. 776–794.], varieties and a logic of inequalities are studied. A proof system with one infinitary inference rule is shown to be complete.