2-сжимающие слова и проблема реконструкции последовательности

Abstract

Для данного слова свойство быть 2-сжимаемым (2-синхронизирующим) существенно зависит от свойств некоторого специального множества S его факторов. Мы изучаем возможность реконструкции 2-сжимающего (2-синхронизирующего) слова по этому множеству. Переходя от множества S ко множеству Xs его факторов длины три, мы показываем, что 2-сжимающее (2-синхронизирующее) слово является накрывающим для Xs.

For a given word the property of being 2-collapsing (2-synchronizing) essentially depends on the properties of a particular set S of its factors. We study whether it is possible to reconstruct a 2-collapsing (2-synchronizing) word from this set. Passing from the set S to the set Xs of its factors of length 3 we show that a 2-collapsing (2-synchronizing) word is a proper overlapping of Xs.