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

Les structures musicales présentent fréquemment des caractéristiques arborescentes ou hiérarchiques. On connait bien les arbres rythmiques subdivisant des unités temporelles, ou encore, peut-être à plus grand échelle, de nombreux exemples d'organisation hiérarchique de formes musicales. Les arbres ont par ailleurs été largement étudiés en informatique, mais peu d'applications musicales fortes ont été issues de ces recherches. Cette séance nous donnera un panorama de récents travaux réalisés dans ce domaine. Séance organisée en partenariat avec l'INRIA.