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.
Type de document :
Communication dans un congrès
Proceedings of the 4th International Conference on Rewriting Techniques and Applications, RTA'91, 1991, Como, Italy. Springer Verlag, 488, pp.287-298, 1991, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00538876
Contributeur : Rémi Gilleron <>
Soumis le : mardi 23 novembre 2010 - 14:47:53
Dernière modification le : mardi 24 avril 2018 - 13:32:52

Identifiants

  • HAL Id : inria-00538876, version 1

Collections

Citation

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. Springer Verlag, 488, pp.287-298, 1991, Lecture Notes in Computer Science. 〈inria-00538876〉

Partager

Métriques

Consultations de la notice

144