Аннотация:
В статье устанавливается NP-полнота задач редактирования слов относительно языка, заданного в терминах ограничений на множество подслов в его словах. Действие операций редактирования состоит в замене подслов редактируемого слова, принадлежащих некоторому блоковому коду, словами другого блокового кода.
Полный текст:
PDF файл (315 kB)