Une machine à états finis déterministes qui accepte des arbres infinis, et non seulement les chaînes. L'arborescence de nœuds sont marqués par les lettres de l'alphabet de l'automate, et la fonction de transition encode les États suivants pour chaque branche de l'arbre. Expressive de la puissance de ces automates varie selon les conditions d'acceptation des arbres.