ON PARALLEL DELETIONS APPLIED TO A WORD

We consider sets arising from a single word by parallel deletion of su bwords belonging to a given language. The issues dealt with are rather basic in language theory and combinatorics of words. We prove that ev ery finite set is a parallel deletion set but a strict hierarchy resul ts from k-bounded parallel deletions. We also discuss decidability, th e parallel deletion number associated to a word and a certain collapse set of a language, as well as point out some open problems.