Частичное слово длины п над алфавитом A есть частичная функция W:{1, ..., n} → A. Частичное слово рассматривают как: обычное слово над алфавитом A_◇ = A∪{◇}, полагая W(i) = ◇ для i таких, что W(i) не определена. Символ ◇ называется джокером. Частичное слово W имеет период р, если W(i) = W(j) для всех W(i), W(j) ∈ A, i ∈ j (mod p). Свойство взаимодействия периодов для периодических слов заключается в следующем: слово с периодами р и д имеет также период НОД(p, q). Выполнение этого свойства для обычных слов зависит только от длины слова, а для частичных слов - от длины слова, а также от числа и расположения джокеров в слове. В данной статье исследуется случай, когда наличие свойства взаимодействия периодов не обусловлено достаточно большой (по сравнению с числом джокеров) длиной, т. е. это свойство может присутствовать или отсутствовать в зависимости от расположения джокеров в слове. Разработан полиномиальный (с фиксированным параметром) алгоритм для определения вероятности выполнения свойства взаимодействия периодов для частичных слов данной длины с данным числом джокеров и приведены результаты полученных экспериментов.
展开▼
