Jean Berstel, Luc Boasson, Olivier Carton, Bruno
Petazzoni et Jean-Éric Pin
Résumé : Filtrer un mot a0a1
... an suivant une suite strictement croissante s de
N consiste à supprimer les lettres ai telles que
i n'appartienne pas à l'ensemble {s0,
s1, ...}. On étend la notation aux langages en notant
L[s], où L est un langage, l'ensemble des mots de
L filtrés par s. Le problème du filtrage
consiste à caractériser les filtres s tels que, pour
tout langage reconnaissable L, L[s] est reconnaissable. Dans
cet article, nous résolvons le problème du filtrage et nous
donnons une approche unifiée pour résoudre des questions
similaires, et notamment le "removal problem" considéré par
Seiferas and McNaughton. Notre approche repose sur une étude
détaillée de diverses notions résiduelles,
notamment celles de suites résiduellement ultimement
périodiques et de transduction résiduellement rationnelle.
Abstract : Given a strictly increasing sequence s of
non-negative integers, filtering a word a0a1 ...
an by s consists in deleting the letters ai
such that i is not in the set {s0, s1,
...}. By a natural generalization, denote by L[s], where
L is a language, the set of all words of L filtered by
s. The filtering problem is to characterize the filters s
such that, for every regular language L, L[s] is
regular. In this paper, the filtering problem is solved, and a unified
approach is provided to solve similar questions, including the removal
problem considered by Seiferas and McNaughton. Our approach relies on a
detailed study of various residual notions, notably residually
ultimately periodic sequences and residually rational transductions.