Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Rémi Gilleron Connect in order to contact the contributor
Submitted on : Tuesday, November 23, 2010 - 2:48:38 PM
Last modification on : Friday, January 8, 2021 - 11:22:05 AM


  • HAL Id : inria-00538881, version 1



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⟩



Record views