One-Rule Length-Preserving Rewrite Systems and Rational Transductions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 2, pp. 149-171.

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.

DOI : https://doi.org/10.1051/ita/2013044
Classification : 68Q45,  68Q42,  68R15
Mots clés : string rewriting - rationality
@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},
pages = {149--171},
publisher = {EDP-Sciences},
volume = {48},
number = {2},
year = {2014},
doi = {10.1051/ita/2013044},
mrnumber = {3302482},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2013044/}
}
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) no. 2, pp. 149-171. doi : 10.1051/ita/2013044. http://www.numdam.org/articles/10.1051/ita/2013044/

[1] J. Berstel, Transductions and Context-Free Languages. Teubner Verlag (1979). | MR 549481 | Zbl 0424.68040

[2] M. Clerbout and Y. Roos, 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] N. Dershowitz, 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] S. Eilenberg and B. Tilson, Automata, languages and machines, vol. B, Pure Appl. Math. Academic Press, New York, San Francisco, London (1976). | MR 530383 | Zbl 0317.94045

[5] A. Geser, 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] A. Geser, D. Hofbauer, and J. Waldmann, Match-bounded string rewriting systems. Appl. Algebra Eng. Commun. Comput. 15 (2004) 149-171. | MR 2104291 | Zbl 1101.68048

[7] W. Kurth, Termination und Konfluenz von Semi-Thue-Systemen mit nur einer Regel. Ph.D. thesis, Technische Universitt Clausthal (1990). | Zbl 0719.03019

[8] M. Latteux and Y. Roos, 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] É. Lilin, 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] Y. Métivier, 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] R. Milner, 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] B. Ravikumar, Peg-solitaire, string rewriting systems and finite automata. Theor. Comput. Sci. 321 (2004) 383-394. | MR 2076153 | Zbl 1068.68073

[13] J. Sakarovitch, Elements of Automata Theory. Cambridge University Press, New York, USA (2009). | MR 2567276 | Zbl 1188.68177

[14] J. Sakarovitch and I. Simon, Subwords. In Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press (1997) 105-142.

[15] A. Terlutte and D. Simplot, Iteration of rational transductions. RAIRO: ITA 34 (2000) 99-130. | Numdam | MR 1774304 | Zbl 0962.68090

[16] C. Wrathall, 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