One-Rule Length-Preserving Rewrite Systems and Rational Transductions
Michel Latteux, Yves Roos (2014)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We address the problem to know whether the relation induced by a one-rule length-preserving rewrite system is rational. We partially answer to a conjecture of Éric Lilin who conjectured in 1991 that a one-rule length-preserving rewrite system is a rational transduction if and only if the left-hand side and the right-hand side of the rule of the system are not quasi-conjugate or are equal, that means if and are distinct, there do not exist words , and such that = and = . We prove...