BOTTOM-UP TREE PUSHDOWN-AUTOMATA - CLASSIFICATION AND CONNECTION WITHREWRITE SYSTEMS

We define different types of bottom-up tree pushdown automata and stud y their connections with rewrite systems. Along this line of research we complete and generalize the results of Gallier, Book and Salomaa. W e define the notion of a tail-reduction-free (trf) rewrite system. Usi ng the decidability of ground reducibility, we prove the decidability of the trf property. Monadic rewrite systems of Book, Gallier and Salo maa become a natural particular case of trf rewrite systems. We associ ate a deterministic bottom-up tree pushdown automaton with any left-li near trf rewrite system. Finally, we generalize monadic rewrite system s by introducing the notion of a semi-monadic rewrite system and show that, like a monadic rewrite system, it preserves recognizability.