Jean Berstel, Luc Boasson, Olivier Carton, Bruno
Petazzoni et Jean-Éric Pin
Résumé : Filtrer un mot a0a1 ...
an suivant une partie S de N consiste à
supprimer les lettres ai telles que i n'appartienne pas
à S. 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 utilise deux ingrédients
principaux: le premier est la notion de suite résiduellement
ultimement périodique et la seconde est la notion de transduction
représentable.
Abstract : Given a subset S of N, filtering a word
a0a1 ... an by S consists in
deleting the letters ai such that i is not in S. 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 recognizable language L, L[S] is recognizable. 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. There are two main ingredients on our approach: the
first one is the notion of residually ultimately periodic sequences, and the
second one is the notion of representable transductions.