Operations preserving recognizable languages

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.

PostScript file compressed with gzip, PDF file


Valid HTML 4.01!