Bottom-up Tree Pushdown Automata: Classification and Connection with Rewrite Systems

Abstract : We define different types of bottom-up tree pushdown automata and study their connections with rewrite systems. Along this line of research we complete and generalize the results of Gallier, Book and Salomaa. We define the notion of a tail-reduction-free (trf) rewrite system. Using the decidability of ground reducibility, we prove the decidability of the trf property. Monadic rewrite systems of Book, Gallier and Salomaa become a natural particular case of trf rewrite systems. We associate a deterministic bottom-up tree pushdown automaton with any left-linear trf rewrite system. Finally, we generalize monadic rewrite systems by introducing the notion of a semi-monadic rewrite system and show that, like a monadic rewrite system, it preserves recognizability.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 1994, 127 (1), pp.69--98
Liste complète des métadonnées

https://hal.inria.fr/inria-00538881
Contributeur : Rémi Gilleron <>
Soumis le : mardi 23 novembre 2010 - 14:48:38
Dernière modification le : jeudi 17 mai 2018 - 12:52:03

Identifiants

  • HAL Id : inria-00538881, version 1

Collections

Citation

Jean-Luc Coquidé, Max Dauchet, Rémi Gilleron, Sandor Vágvölgyi. Bottom-up Tree Pushdown Automata: Classification and Connection with Rewrite Systems. Theoretical Computer Science, Elsevier, 1994, 127 (1), pp.69--98. 〈inria-00538881〉

Partager

Métriques

Consultations de la notice

210