Rational Infinite Trees

Appeared in Volume 8/1, February 1995

smk@dcs.ed.ac.uk
Stefan Kahrs
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.

Some references:

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)

treinen@dfki.uni-sb.de
Ralf Treinen
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

mark@omnifest.uwm.edu
Mark Hopkins
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.