One-Rule Length-Preserving Rewrite Systems and Rational Transductions

Michel Latteux; Yves Roos

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

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

Abstract

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

How to cite

top

Latteux, 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. [1] J. Berstel, Transductions and Context-Free Languages. Teubner Verlag (1979). Zbl0424.68040MR549481
  2. [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. [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. [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. [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. [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. [7] W. Kurth, Termination und Konfluenz von Semi–Thue–Systemen mit nur einer Regel. Ph.D. thesis, Technische Universitt Clausthal (1990). Zbl0719.03019
  8. [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. [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. [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. [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. [12] B. Ravikumar, Peg-solitaire, string rewriting systems and finite automata. Theor. Comput. Sci.321 (2004) 383–394. Zbl1068.68073MR2076153
  13. [13] J. Sakarovitch, Elements of Automata Theory. Cambridge University Press, New York, USA (2009). Zbl1188.68177MR2567276
  14. [14] J. Sakarovitch and I. Simon, Subwords. In Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press (1997) 105–142. 
  15. [15] A. Terlutte and D. Simplot, Iteration of rational transductions. RAIRO: ITA 34 (2000) 99–130. Zbl0962.68090MR1774304
  16. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.