## Deletion sets.(English)Zbl 0787.68062

Given a string $$w$$ and a language $$L$$, one considers the (finite) set of all strings obtained by erasing from $$w$$ a substring which belongs to $$L$$; this set (let us denote it by $$D(w,L)$$) is called deletion set. The notion has been introduced and briefly investigated by the first author [On insertion and deletion operations in formal languages, PhD Thesis, Univ. of Turku, Dept. of Math., 1991].
In the present paper, the deletion sets are more systematically investigated, mainly from the following four points of view: how large $$D(w,L)$$ can be depending on the structure of $$w$$, deciding whether a given set is a deletion set (positive answer), characterizations of deletion sets (combinatorial and algebraical approaches), CF-decidability (a deletion set $$F$$ is CF-decidable if given a context-free language $$L$$ it is decidable whether or not a string $$w$$ exists such that $$F = D(w,L)$$; it is proved that no set $$F$$ different from $$\{\lambda\}$$ is CF- decidable; Theorem 5.36 in the above mentioned thesis says that every finite set is REG-decidable).
Reviewer: G.Paun

### MSC:

 68Q45 Formal languages and automata 68R15 Combinatorics on words

### Keywords:

decidability; deletion sets