by Jean Berstel, Luc Boasson, Olivier Carton, Bruno Petazzoni and Jean-Éric Pin
Étant donné un sous-ensemble S de N, filtrer un mot a0a1…an par S consiste à effacer les lettres ai telles que i n'appartient pas à S. De manière plus générale, on note L[S], où L est un langage, l'ensemble de tous les mots de L filtrés par S. Le problème de filtrage est de caractériser les filtres S, tels que pour tout ensemble reconnaissable L, L[S] est aussi reconnaissable. Dans cet article, le problème du filtrage est résolu et une approche unifiée est donnée pour résoudre des questions similaires comme le problème de la suppression considéré par Seiferas et McNaughton. Il y a deux ingrédients essentiels dans notre approche. Le premier est la notion de suite résiduellement ultimement périodique. Le second est la notion de transduction représentable.
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.
PostScript Files