Abstract FR:

La réécriture est, à plusieurs titres, un paradigme bien connu de la programmation. Notre but est de contribuer à mieux comprendre les structures algébriques complexes manipulées. Nous prouvons que les systèmes clos munis d'un contrôle reconnaissable ont la même puissance que les systèmes généraux. Nous montrons que les ensembles d'arbres de dérivation dans les problèmes d'accessibilité peuvent être vus comme des forêts reconnaissables. Enfin, nous introduisons une notion qui permet d'éclairer et de généraliser les études antérieures sur les liens entre systèmes de réécriture et automates à piles.