Rational tree relations
Jean-Claude Raoult · Bulletin of the Belgian Mathematical Society - Simon Stevin · 1997
We investigate forests and relations on trees generated by grammars in which the non-terminals represent relations.This introduces some synchronization between productions.We show that these sets are also solutions of systems of equations, that they are described by rational expressions involving union, substitution and iterated substitution, and that they are preserved by residuals.We show that they are the images of k-copying descending transducers.Finally, we isolate a subset of these relations which is preserved by composition.