Latteux, Michel; Roos, Yves One-rule length-preserving rewrite systems and rational transductions. (English) Zbl 1366.68123 RAIRO, Theor. Inform. Appl. 48, No. 2, 149-171 (2014). Summary: 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 \(u\) and the right-hand side \(v\) of the rule of the system are not quasi-conjugate or are equal, that means if \(u\) and \(v\) are distinct, there do not exist words \(x\), \(y\) and \(z\) such that \(u=xyz\) and \(v=zyx\). We prove the only if part of this conjecture and identify two non trivial cases where the if part is satisfied. Cited in 2 Documents MSC: 68Q42 Grammars and rewriting systems 68R15 Combinatorics on words Keywords:string rewriting; rationality PDFBibTeX XMLCite \textit{M. Latteux} and \textit{Y. Roos}, RAIRO, Theor. Inform. Appl. 48, No. 2, 149--171 (2014; Zbl 1366.68123) Full Text: DOI Link