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.
@article{ITA_2014__48_2_149_0,
author = {Latteux, Michel and Roos, Yves},
title = {One-Rule Length-Preserving Rewrite Systems and Rational Transductions},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {48},
year = {2014},
pages = {149-171},
doi = {10.1051/ita/2013044},
mrnumber = {3302482},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2014__48_2_149_0}
}
Latteux, Michel; Roos, Yves. One-Rule Length-Preserving Rewrite Systems and Rational Transductions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) pp. 149-171. doi : 10.1051/ita/2013044. http://gdmltest.u-ga.fr/item/ITA_2014__48_2_149_0/
[1] , Transductions and Context-Free Languages. Teubner Verlag (1979). | MR 549481 | Zbl 0424.68040
[2] and , Semi-commutations and algebraic languages, in STACS 90, in vol. 415, edited by Christian Choffrut and Thomas Lengauer. Lect. Notes Comput. Sci. Springer Berlin/Heidelberg (1990) 82-94. | MR 1063305 | Zbl 0729.68036
[3] , Open. closed. open, in vol. 3467 of Lect. Notes Comput. Sci. RTA, edited by J. Giesl. Springer (2005) 376-393. | MR 2184558 | Zbl 1078.68653
[4] and , Automata, languages and machines, vol. B, Pure Appl. Math. Academic Press, New York, San Francisco, London (1976). | MR 530383 | Zbl 0317.94045
[5] , Termination of string rewriting rules that have one pair of overlaps, in vol. 2706, Lect. Notes Comput. Sci. RTA, edited by R. Nieuwenhuis. Springer (2003) 410-423. | MR 2071597 | Zbl 1038.68065
[6] , , and , Match-bounded string rewriting systems. Appl. Algebra Eng. Commun. Comput. 15 (2004) 149-171. | MR 2104291 | Zbl 1101.68048
[7] , Termination und Konfluenz von Semi-Thue-Systemen mit nur einer Regel. Ph.D. thesis, Technische Universitt Clausthal (1990). | Zbl 0719.03019
[8] and , The image of a word by a one-rule semi-Thue system is not always context-free (2011). http://www.lifl.fr/ỹroos/al/one-rule-context-free.pdf.
[9] , Une généralisation des semi-commutations. Technical Report IT-210, Laboratoire d'Informatique Fondamentale de Lille, Université de Lille 1, France (1991). In french.
[10] , Calcul de longueurs de chaînes de reé´criture dans le monoïde libre. Theor. Comput. Sci. 35 (1985) 71-87. | MR 785908 | Zbl 0562.03019
[11] , The spectra of words, in vol. 3838 of Processes, Terms and Cycles: Steps on the Road to Infinity, edited by A. Middeldorp, V. van Oostrom, F. van Raamsdonk and R. de Vrijer. Lect. Notes Comput. Sci. Springer Berlin/Heidelberg (2005) 1-5. | Zbl 1171.68655
[12] , Peg-solitaire, string rewriting systems and finite automata. Theor. Comput. Sci. 321 (2004) 383-394. | MR 2076153 | Zbl 1068.68073
[13] , Elements of Automata Theory. Cambridge University Press, New York, USA (2009). | MR 2567276 | Zbl 1188.68177
[14] and , Subwords. In Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press (1997) 105-142.
[15] and , Iteration of rational transductions. RAIRO: ITA 34 (2000) 99-130. | Numdam | MR 1774304 | Zbl 0962.68090
[16] , Confluence of one-rule thue systems, Word Equations and Related Topics, in vol. 572 of Lect. Notes Comput. Sci., edited by K. Schulz. Springer Berlin/Heidelberg (1992) 237-246. | MR 1232039