On morphisms and nested recurrence relations

Marcel Celaya, Department of Mathematics, McGill University, Canada.
Frank Ruskey, Department of Computer Science, University of Victoria, Canada.


We explore a family of nested recurrence relations with arbitrary levels of nesting, which have an interpretation in terms of fixed points of morphisms over a countably infinite alphabet. Recurrences in this family are related to a number of well-known sequences, including Hofstadter's $G$ sequence and the Conolly and Tanny sequences.

Back to list of publications.