One-Rule Length-Preserving Rewrite Systems and Rational Transductions
Laboratoire d’Informatique Fondamentale de Lille, Université Lille 1, France.
Accepted: 3 December 2013
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.
Mathematics Subject Classification: 68Q45 / 68Q42 / 68R15
Key words: String rewriting - rationality
© EDP Sciences 2014