Réduction de la non-linéarité des morphismes d'arbres Recognizable tree-languages and non-linear morphisms

Abstract

Le but de ce papier est d’étudier certaines propriétés des morphismes d'arbres et d’éclairer certains phénomènes complexes propres aux arbres. En particulier, on montre que si l'image par un morphisme quasi-alphabétique d'une forêt reconnaissable est reconnaissable, on peut 《réduire la non linéarité》 du morphisme (en un sens que l'on précisera). Ce résultat nous permet de généraliser le théorème de cross-section.