Properties of gene networks with threshold functions.pdf Пусть n ^ к — натуральные числа. Циклическим словом называется периодическое бесконечное в две стороны слово с периодом n; обозначается а1 a2 ... an. Множество всех циклических слов длины n будем обозначать через Qn. Рассмотрим ориентированный граф Gn,k+1 = (V, E), где множество вершин V равно {v1,... ,vn} (последовательность вершин соответствует циклическому слову), а множество рёбер E такое, что каждая вершина vi имеет входящие рёбра из к предыдущих вершин и выходящие в k следующих вершин. Пороговой функцией называется булева функция, которая представима в виде " k 1 Y, ai Xi > T i=1 ai,T e R. Рассмотрим пороговую функцию f, зависящую от k переменных. Построим отображение Af : Qn ^ Qn, которое каждому слову a1a2 ... an ставит в соответствие слово b1b2 .. .bn, если bi = f (ai-k, ai-k+1, . . . , ai-1) для всех i e {1,...,n}. Неподвижной точкой отображения Af называется слово а, такое, что а = Af (а). Циклическое слово а называется истоком для отображения Af : Qn ^ Qn, если не существует слова в, такого, что Af (в) = а. Графом состояний отображения Af : Пга Т Пга называется ориентированный граф, в котором Пга — множество вершин, а дуги соединяют слова а и в, если в = Af (а). Данная работа посвящена описанию свойств графа состояний отображения Af, а именно описанию истоков, неподвижных точек и циклических состояний, нахождению длин максимальных цепочек. Пусть f — булева функция от к переменных. Построим ориентированный граф Pf, вершинами которого являются все возможные слова длины к, а рёбра соединяют слова x1 ... xk и x2 ... xkb, если f (xi,... , xk) = b. Следующая теорема содержит способ нахождения всех неподвижных точек графов состояния отображения Af для произвольной булевой функции от к переменных. Теорема 1. Пусть f — булева функция от к переменных и n кратно l. Граф Pf содержит простой цикл (v1,...,vl), где v = Xj . ..xk+i-1 для i G {1,...,l}, тогда и только тогда, когда (x1... Xi)n/l является неподвижной точкой графа состояний отображения Af. В следующей теореме описаны все истоки графа состояний отображения. Теорема 2. Пусть f — булева функция от к переменных и существует единственный набор значений переменных v, такой, что f (v) = 1. Тогда циклическое слово а длины n является истоком графа состояний отображения Af тогда и только тогда, когда оно удовлетворяет одному из условий: 1) а содержит подслово 10s-11, где 1 ^ s ^ к — 1 и s = s'; 2) а содержит подслово 10k-11, где к = is' и t ^ 2. Здесь s' — минимальный период слова v. Получено описание всех циклов и длин максимальных цепочек для графа состояний отображения Af, где f — булева функция от трёх переменных, удовлетворяющая условию предыдущей теоремы. Если f(0, 0, 0) = 1, то циклы этого графа представляют циклический сдвиг на 1, 2 или 3 позиции состояния, избегающего определённые слова.

Скачать электронную версию публикации