Skip to Main content Skip to Navigation
Journal articles

One-rule length-preserving rewrite systems and rational Transductions

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00934621
Contributor : Yves Roos <>
Submitted on : Wednesday, January 22, 2014 - 12:59:02 PM
Last modification on : Monday, December 16, 2019 - 3:30:49 PM

Links full text

Identifiers

Citation

Michel Latteux, Yves Roos. One-rule length-preserving rewrite systems and rational Transductions. RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), EDP Sciences, 2014, 48 (2), pp.149-171. ⟨10.1051/ita/2013044⟩. ⟨hal-00934621⟩

Share

Metrics

Record views

224