Аннотация. Рассматривается расширение задачи реконструкции слов по заданному мультимножеству подслов, предположительно порожденных смещением окна фиксированной длины со сдвигом 1. Это связано с наличием дополнительных ограничений на допустимые решения. Изучен случай, когда эти ограничения определяются запрещенными словами. Получено решение задачи, основанное на поиске эйлеровых путей в мультиорграфе де Брейна с дополнительной операцией редукции ребер и применением специальных алгебраических операций умножения матриц смежности, определенных в первой части статьи.
Ключевые слова: реконструкция слов, запрещенное слово, эйлеровы пути, мультиорграф де Брейна, комбинаторика слов.
Сметанин Юрий Геннадиевич,
доктор физ.-мат. наук, главный научный сотрудник Вычислительного центра им. А.А. Дородницына РАН, Москва; профессор Московского физико-технического института, Россия,
e-mail: ysmetanin@rambler.ru.
Ульянов Михаил Васильевич,
доктор техн. наук, профессор Научно-исследовательского университета «Высшая школа экономики», Москва;
профессор Московского государственного университета печати имени Ивана Федорова, Россия,
e-mail: muljanov@mail.ru.