On rationally controlled one-rule insertion systems

Latteux, Michel; Roos, Yves

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1051/ita/2022008

Titre :

On rationally controlled one-rule insertion systems

Auteur(s) :

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

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

Titre de la revue :

RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

Pagination :

Éditeur :

EDP Sciences

Date de publication :

2022

ISSN :

0988-3754

Mot(s)-clé(s) en anglais :

String rewriting
context-free languages

Discipline(s) HAL :

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

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :