О сложности некоторых задач редактирования слов

Редактированием слова $S$ относительно языка $L$ называется процедура выбора минимальной последовательности операций из заданного набора операций $\varPhi$, переводящей $S$ в какое-либо слово из $L$. В предположении, что набор $\varPhi$ состоит из операций удаления букв, вставки букв, замены одной буквы другой и перестановки пары букв, устанавливается $NP$-полнота задачи редактирования относительно языка $L$ с ограничениями на множество подслов, встречающихся в словах языка.