# One-Rule Length-Preserving Rewrite Systems and Rational Transductions

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

- Volume: 48, Issue: 2, page 149-171
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topLatteux, Michel, and Roos, Yves. "One-Rule Length-Preserving Rewrite Systems and Rational Transductions." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.2 (2014): 149-171. <http://eudml.org/doc/273008>.

@article{Latteux2014,

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.},

author = {Latteux, Michel, Roos, Yves},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {string rewriting - rationality},

language = {eng},

number = {2},

pages = {149-171},

publisher = {EDP-Sciences},

title = {One-Rule Length-Preserving Rewrite Systems and Rational Transductions},

url = {http://eudml.org/doc/273008},

volume = {48},

year = {2014},

}

TY - JOUR

AU - Latteux, Michel

AU - Roos, Yves

TI - One-Rule Length-Preserving Rewrite Systems and Rational Transductions

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2014

PB - EDP-Sciences

VL - 48

IS - 2

SP - 149

EP - 171

AB - 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.

LA - eng

KW - string rewriting - rationality

UR - http://eudml.org/doc/273008

ER -

## References

top- [1] J. Berstel, Transductions and Context-Free Languages. Teubner Verlag (1979). Zbl0424.68040MR549481
- [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. Zbl0729.68036MR1063305
- [3] N. Dershowitz, Open. closed. open, in vol. 3467 of Lect. Notes Comput. Sci. RTA, edited by J. Giesl. Springer (2005) 376–393. Zbl1078.68653MR2184558
- [4] S. Eilenberg and B. Tilson, Automata, languages and machines, vol. B, Pure Appl. Math. Academic Press, New York, San Francisco, London (1976). Zbl0317.94045MR530383
- [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. Zbl1038.68065MR2071597
- [6] A. Geser, D. Hofbauer, and J. Waldmann, Match-bounded string rewriting systems. Appl. Algebra Eng. Commun. Comput.15 (2004) 149–171. Zbl1101.68048MR2104291
- [7] W. Kurth, Termination und Konfluenz von Semi–Thue–Systemen mit nur einer Regel. Ph.D. thesis, Technische Universitt Clausthal (1990). Zbl0719.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. Zbl0562.03019MR785908
- [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. Zbl1171.68655
- [12] B. Ravikumar, Peg-solitaire, string rewriting systems and finite automata. Theor. Comput. Sci.321 (2004) 383–394. Zbl1068.68073MR2076153
- [13] J. Sakarovitch, Elements of Automata Theory. Cambridge University Press, New York, USA (2009). Zbl1188.68177MR2567276
- [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. Zbl0962.68090MR1774304
- [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. MR1232039

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.