LINEAR GENERALIZED SEMI-MONADIC REWRITE SYSTEMS EFFECTIVELY PRESERVE RECOGNIZABILITY

We introduce the notion of the generalized semi-monadic rewrite system , which is a generalization of well-known rewrite systems: the ground rewrite system, the monadic rewrite system, and the semi-monadic rewri te system. We show that linear generalized semi-monadic rewrite system s effectively preserve recognizability. We show that a tree language L is recognizable if and only if there exists a rewrite system R such t hat R boolean OR R-1 is a linear generalized semi-monadic rewrite syst em and that L is the union of finitely many <->(R)-classes. We show s everal decidability and undecidability results on rewrite systems effe ctively preserving recognizability and on generalized semi-monadic rew rite systems. For example, we show that for a rewrite system R effecti vely preserving recognizability, it is decidable if R is locally confl uent. Moreover, we show that preserving recognizability and effectivel y preserving recognizability are modular properties of linear collapse -free rewrite systems. Finally, as a consequence of our results on tre es we get that restricted right-left overlapping string rewrite system s effectively preserve recognizability.