Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-18T09:36:07.207Z Has data issue: false hasContentIssue false

One-Rule Length-Preserving Rewrite Systems and RationalTransductions

Published online by Cambridge University Press:  21 January 2014

Michel Latteux
Affiliation:
Laboratoire d’Informatique Fondamentale de Lille, Université Lille 1, France.. yves.roos@lifl.fr
Yves Roos
Affiliation:
Laboratoire d’Informatique Fondamentale de Lille, Université Lille 1, France.. yves.roos@lifl.fr

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We address the problem to know whether the relation induced by a one-rulelength-preserving rewrite system is rational. We partially answer to a conjecture of ÉricLilin who conjectured in 1991 that a one-rule length-preserving rewrite system is arational transduction if and only if the left-hand side u and theright-hand side v of the rule of the system are not quasi-conjugate orare equal, that means if u and v are distinct, there donot exist words x, y and z such thatu = xyz and v = zyx.We prove the only if part of this conjecture and identify two non trivialcases where the if part is satisfied.

Information

Type
Research Article
Copyright
© EDP Sciences 2014