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