ON PARALLEL DELETIONS APPLIED TO A WORD

摘要

Nous considérons les ensembles produits à partir d'un mot par l'effacement en parallèle de facteurs appartenant à un langage donné. Ces problèmes sont de nature fondamentale dans la théorie des langages et en combinatoire des mots. Nous prouvons que tout ensemble fini est un ensemble obtenu par effacement parallèle, et qu'il existe une hiérarchie stricte en se bornant à k effacements parallèles. Nous examinons également la décidabilité, le nombre d'effacement parallèle associé à un mot, et un certain ensemble d'écroulement d'un langage. Nous mentionnons aussi quelques problèmes ouverts.%We consider sets arising from a single word by parallel deletion of subwords belonging to a given language. The issues dealt with are rather basic in language theory and combinatorics of words. We prove that every finite set is a parallel deletion set but a strict hierarchy results from k-bounded parallel deletions. We also discuss decidability, the parallel deletion number associated to a word and a certain collapse set of a language, as well as point out some open problems.