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


68Q45 Formal languages and automata
68R15 Combinatorics on words