Abstract:
By the editing of a word $S$ with respect to a language $L$ is meant a procedure for choosing a minimal sequence of operations from a given set of operations $\varPhi$ that translates $S$ into some word of $L$. Under the assumption that the set $\varPhi$ consists of operations of removal of letters, insertion of letters, replacement of one letter by another and transposition of a pair of letters, we establish $NP$-completeness of a problem of editing with respect to language $L$ with constraints on the set of subwords that occur in words of the language.