De la même manière qu'un automate d'états finis classique lit des mots donnés en entrée, un automate d'arbres va parcourir un arbre étiqueté, l'acceptant ou non à la fin du parcours. Ce modèle de calcul peut servir alternativement de description finie d'ensembles d'arbres infinis (langages d'arbres), comme par exemple l'ensemble des solutions d'un système de contraintes symboliques, afin d'aider au raisonnement sur les contraintes, grâce à des algorithmes efficaces de composition et de décision sur les automates d'arbres. Motivés par les contraintes de rythme en aide à la composition, nous verrons quelques applications de cette approche aux contraintes de type et d'intégrité pour les données Web, et au problèmes d'accessibilité pour des programmes fonctionnels ou impératifs (technique dite de model checking régulier).

Arbres et structures hiérarchiques en informatique musicale