Appeared in Volume 8/1, February 1995
12th September 1994
Mark Hopkins writes:
Who else besides Colmerauer (in his formulation of Prolog-II) does something with rational infinite trees? Or larger classes of infinite trees? In his presentations he provided no prior references to the concept.
Cardone/Coppo, "Two extensions of Curry's Type Inference System" in P. Odifreddi (ed.) "Logic and Computer Science", Academic Press 1990. The "recursive types" extension uses regular trees.
Ariola/Klop, "Cyclic Lambda Graph Rewriting" in proceedings LICS'94. It doesn't mention regular trees (as far as I remember), but "trees+cycles" are exactly the same thing.
Goubalt/Hankin, "A Lattice for the Abstract Interpretation of Term Graph Rewriting Systems" in Sleep/Plasmeijer/van Eekelen "Term Graph Rewriting", John Wiley 1993
An earlier reference is:
Courcelle, "Fundamental properties of infinite trees" TCS 25, 95-169 (1983)
12th September 1994
Some work on rational and arbitrary infinite trees has been done here at DFKI. We are using feature trees, where, in contrast to Colmerauer's formalisation, the edges are labelled with feature symbols. Features are always functional. You could view this as a language with selector functions, whereas the classical view is to take constructor functions.
Here is list of recent references. Most of the papers are available by anonymous ftp from ftp://ps-ftp.dfki.uni-sb.de/pub/papers/ProgrammingSysLab/ or via WWW at http://ps-www.dfki.uni-sb.de/papers/. The first one is probably the most interesting one from a logic programming perspective.
Gert Smolka and Ralf Treinen, Records for Logic Programming, JLP, Vol. 18, No. 3, 1994, April, pp.229-258
Hassan Aït-Kaci and Andreas Podelski and Gert Smolka, A Feature-based Constraint System for Logic Programming with Entailment, TCS, 1994, Jan, Vol. 122, No.1-2, pp.263-283
Rolf Backofen and Ralf Treinen, How to Win a Game with Features, In 1st Int. Conf. on Constraints in Computational Logics, Jean-Pierre Jouannaud (ed.), LNCS, vol. 845, pp.320-335, Springer
Rolf Backofen and Gert Smolka, A Complete and Recursive Feature Theory, 31th Annual Meeting of the Assoc. for Computational Linguistics, 1993, pp.193-200, Assoc. for Computational Linguistics
Ralf Treinen, Feature Constraints with First-Class Features, In "Mathematical Foundations of Computer Science", Andrzej M. Borzyszkowski and Stefan Sokolowski (ed.), 1993, Springer, pp.734-743, LNCS, vol. 711
Rolf Backofen, Regular Path Expressions in Feature Logic, JSC, Vol. 17, pp.421-455, 1994
15th December 1994
I'm not entirely sure anymore whether the Ariola/Klop reference is dealing with regular infinite trees as trees+cycles or just recursive combinators. The latter is not the same thing with respect to functional language programming, since it involves a subtly different reduction process than true regular infinite lambda terms.
I've written articles in the comp.lang.functional newsgroup on the Lambda Calculus for regular infinite trees, the description and derivation of a reduction architecture for them (the SEQCD machine), and a cursory description of its relation to intra-procedural control flow structures in imperative languages.
All these are available from me by e-mail.