On Rationally Controlled One-Rule Insertion Systems
RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 8

Rationally controlled one-rule insertion systems are one-rule string rewriting systems for which the rule, that is to insert a given word, may be applied in a word only behind a prefix that must belong to a given rational language called the control language. As for general string rewriting systems, these controlled insertion systems induce a transformation over languages: from a starting word, one can associate all its descendants. In this paper, we investigate the behavior of these systems in terms of preserving the classes of languages: finite, rational and context-free languages. We show that, even for very simple such systems, the images of finite or rational languages need not be context-free. In the case when the control language is in the form u* for some word u, we characterize one-rule insertion systems that induce a rational transduction and we prove that for these systems, the image of any context-free language is always context-free.

DOI : 10.1051/ita/2022008
Classification : 68Q45, 68Q42, 68R15
Keywords: String rewriting, context-free languages 
@article{ITA_2022__56_1_A8_0,
     author = {Latteux, Michel and Roos, Yves},
     title = {On {Rationally} {Controlled} {One-Rule} {Insertion} {Systems}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     doi = {10.1051/ita/2022008},
     mrnumber = {4496048},
     zbl = {1520.68063},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2022008/}
}
TY  - JOUR
AU  - Latteux, Michel
AU  - Roos, Yves
TI  - On Rationally Controlled One-Rule Insertion Systems
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2022
VL  - 56
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2022008/
DO  - 10.1051/ita/2022008
LA  - en
ID  - ITA_2022__56_1_A8_0
ER  - 
%0 Journal Article
%A Latteux, Michel
%A Roos, Yves
%T On Rationally Controlled One-Rule Insertion Systems
%J RAIRO. Theoretical Informatics and Applications
%D 2022
%V 56
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2022008/
%R 10.1051/ita/2022008
%G en
%F ITA_2022__56_1_A8_0
Latteux, Michel; Roos, Yves. On Rationally Controlled One-Rule Insertion Systems. RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 8. doi: 10.1051/ita/2022008

[1] J. Berstel , Transductions and context-free languages, vol. 38 of Teubner Studienbücher : Informatik. Teubner (1979). | MR | Zbl

[2] D. Caucal , On the regular structure of prefix rewriting, Theor. Comput. Sci. 106 (1992) 61–86. | MR | Zbl | DOI

[3] L. Chottin , Strict deterministic languages and controlled rewriting systems, in Automata, Languages and Programming, 6th Colloquium, Graz, Austria, July 16-20, 1979, Proceedings, Lecture Notes in Computer Science, edited by H. A. Maurer . vol. 71, Springer (1979) 104–117. | MR | Zbl

[4] L. Chottin , Langages Algébriques et Systèmes de Réécriture Rationels. ITA 16 (1982) 93–112. | MR | Zbl | Numdam

[5] M. Clerbout and Y. Roos , Semi-commutations and algebraic languages, edited by C. Choffrut and T. Lengauer , STACS 90, vol. 415, Lecture Notes in Computer Science. Springer Berlin/Heidelberg (1990) 82–94. | MR | Zbl | DOI

[6] A. Geser , Decidability of termination of grid string rewriting rules. SIAM J. Comput. 31 (2002) 1156–1168. | MR | Zbl | DOI

[7] A. Geser , D. Hofbauer and J. Waldmann , Match-bounded string rewriting systems. Appl. Algebra Eng. Commun. Comput. 15 (2004) 149–171. | MR | Zbl | DOI

[8] A. Geser , D. Hofbauer and J. Waldmann , Termination proofs for string rewriting systems via inverse match-bounds. J. Autom. Reason. 34 (2005) 365–385. | MR | Zbl | DOI

[9] D. Hofbauer and J. Waldmann , Deleting string rewriting systems preserve regularity, Theor. Comput. Sci. 327 (2004) 301–317. | MR | Zbl | DOI

[10] M. Latteux and Y. Roos , On one-rule grid semi-thue systems. Fundam. Inform. 116 (2012) 189–204. | MR | Zbl | DOI

[11] M. Latteux and Y. Roos , On prefixal one-rule string rewrite systems. Theor. Comput. Sci. 795 (2019) 240–256. | MR | Zbl | DOI

[12] P. Leupold , On regularity-preservation by string-rewriting systems, edited by C. Martĺn-Vide , F. Otto and H. Fernau , Language and Automata Theory and Applications, Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers, Lecture Notes in Computer Science, vol. 5196, Springer (2008) 345–356. | MR | Zbl

[13] R. C. Lyndon and M. P. Schutzenberger , The equation aM =bNcP in a free group. Michigan Math. J. 9 (1962) 289–298. | MR | Zbl | DOI

[14] R. Mcnaughton , Semi-Thue systems with an inhibitor. J. Autom. Reason. 26 (2001) 409–431. | MR | Zbl | DOI

[15] M. Nivat , Transductions des langages de Chomsky. Ann. l'Inst. Fourier 18 (1968) 339–455. | MR | Zbl | Numdam | DOI

[16] J. Sakarovitch , Elements of Automata Theory, Cambridge University Press, New York, NY, USA (2009). | MR | Zbl | DOI

[17] G. Sénizergues , Some decision problems about controlled rewriting systems. Theor. Comput. Sci. 71 (1990) 281–346. | MR | Zbl | DOI

[18] G. Sénizergues , Formal languages & word-rewriting, edited by H. Comon and J.-P. Jounnaud , Term Rewriting: French Spring School of Theoretical Computer Science Font Romeux, France, May 17-21, 1993 Advanced Course, Springer Berlin Heidelberg, Berlin, Heidelberg (1995) 75–94. | MR | DOI

Cité par Sources :