×

One-rule length-preserving rewrite systems and rational transductions. (English) Zbl 1366.68123

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.

MSC:

68Q42 Grammars and rewriting systems
68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI Link