Abstract FR:

Les grammaires deterministes de graphes permettent la generation de graphes infinis appeles graphes a motifs. Parmi ceux-ci on distingue la classe des graphes algebriques qui sont les graphes de transition des automates a pile. Une sous-classe propre des graphes algebriques est celle des graphes alphabetiques qui sont les graphes de transition des grammaires algebriques. On donne une condition necessaire et suffisante pour qu'un graphe algebrique soit alphabetique. Une grammaire deterministe de graphes etant donnee, on dispose d'un algorithme qui determine si le graphe a motifs qu'elle engendre est alphabetique, et dans l'affirmative, donne la grammaire algebrique dont le graphe de transition est ce meme graphe a motifs