Том 11, серия 1, номер 4, 2004 г., Стр. 20-35

УДК 519.114
Ю. В. Гамзова
Статистические закономерности взаимодействия периодов частичных слов

Аннотация:
Частичное слово длины $n$ над алфавитом $A$ есть частичная функция $W\colon\{1,\dots,n\}\to A$. Частичное слово рассматривают как обычное слово над алфавитом $A_{\Diamond}=A\cup\{\Diamond\}$, полагая $W(i)=\Diamond$ для $i$ таких, что $W(i)$ не определена. Символ $\Diamond$ называется джокером.
Частичное слово $W$ имеет период $p$, если $W(i)=W(j)$ для всех $W(i),W(j)\in A$, $i\equiv j$ $(\operatorname{mod}p)$. Свойство взаимодействия периодов для периодических слов заключается в следующем: слово c периодами $p$ и $q$ имеет также период НОД$(p,q)$. Выполнение этого свойства для обычных слов зависит только от длины слова, а для частичных слов – от длины слова, а также от числа и расположения джокеров в слове. В данной статье исследуется случай, когда наличие свойства взаимодействия периодов не обусловлено достаточно большой (по сравнению с числом джокеров) длиной, т.е. это свойство может присутствовать или отсутствовать в зависимости от расположения джокеров в слове. Разработан полиномиальный (с фиксированным параметром) алгоритм для определения вероятности выполнения свойства взаимодействия периодов для частичных слов данной длины с данным числом джокеров и приведены результаты полученных экспериментов.

Гамзова Ю. В. ¹
1. Уральский гос. университет,
пр. Ленина, 51, 620083 г. Екатеринбург, Россия
е-mail: snarl@r66.ru

Статья поступила 18 августа 2004 г.