Skip to Main content Skip to Navigation
Conference papers

Bottom-Up Tree Pushdown Automata and Rewrite Systems

Abstract : Studying connections between term rewrite systems and bottom-up tree pushdown automata (tpda), we complete and generalize results of Gallier, Book and K. Salomaa. We define the notion of tail reduction free rewrite systems (trf rewrite systems). Using the decidability of inductive reducibility (Plaisted), we prove the decidability of the trf property. Monadic rewrite systems of Book, Gallier and K. Salomaa become an obvious particular case of trf rewrite systems. We define also semi-monadic rewrite systems which generalize monadic systems but keep their fair properties. We discuss different notions of bottom-up tree pushdown automata, that can be seen as the algorithmic aspect of classes of problems specified by trf rewrite systems. Especially, we associate a deterministic tpda with any left-linear trf rewrite system.
Document type :
Conference papers
Complete list of metadata
Contributor : Rémi Gilleron <>
Submitted on : Tuesday, November 23, 2010 - 2:47:53 PM
Last modification on : Tuesday, April 28, 2020 - 11:52:08 AM


  • HAL Id : inria-00538876, version 1



Jean-Luc Coquidé, Max Dauchet, Rémi Gilleron, Sandor Vágvölgyi. Bottom-Up Tree Pushdown Automata and Rewrite Systems. Proceedings of the 4th International Conference on Rewriting Techniques and Applications, RTA'91, 1991, Como, Italy. pp.287-298. ⟨inria-00538876⟩



Record views