Right-linear finite path overlapping term rewriting systems effectively preserve recognizability

摘要

Right-linear finite path overlapping TRS are shown to effectively preserve recognizability. The class of right-linear finite path overlapping TRS properly includes the class of linear generalized semi-monadic TRS and the class of inverse left-linear growing TRS, which are known to effectively preserve recognizability. Approximations by inverse right-linear finite path overlapping TRS are also discussed.