On rationally controlled one-rule insertion systems

Latteux, Michel; Roos, Yves

Document type :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1051/ita/2022008

Title :

On rationally controlled one-rule insertion systems

Author(s) :

Latteux, Michel [Auteur]
Roos, Yves [Auteur correspondant]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]

Journal title :

RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

Pages :

Publisher :

EDP Sciences

Publication date :

2022

ISSN :

0988-3754

English keyword(s) :

String rewriting
context-free languages

HAL domain(s) :

Informatique [cs]/Théorie et langage formel [cs.FL]
Mathématiques [math]

English abstract : [en]

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 ...
Show more >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.Show less >

Language :

Anglais

Popular science :

Non

Collections :