About transitive property of mappings associated with a finite state machines from the groups as_P.pdf Под детерминированным автоматом будем понимать пятёрку объектов A = = (S, X, Y, 8, Л), где S - множество состояний; X - входной алфавит; Y - выходной алфавит; 8 : S х X ^ S - функция переходов; Л : S х X ^ Y - функция выходов. Для всех рассматриваемых в работе автоматов |S|, |X|, |Y| e N и X = Y = = {0,1,... ,p - 1}, p - простое. Пусть X* обозначает множество всех конечных слов над алфавитом X. Действие функций 8 и Л можно расширить на множество слов X* следующими рекуррентными правилами: 8(s,x • w) = 8(8(s,x), w), Л(з,x • w) = Л(в,x) • Л(8(в,x), w), x e X, w e X*. Автомат с выделенным начальным состоянием называют инициальным. Инициальный автомат будем обозначать через As, где s - начальное состояние автомата. Каждый инициальный автомат As определяет отображение /as : X* ^ Y*, называемое автоматным, такое, что /As(w) = Л^^). Автоматное отображение / называют транзитивным на словах длины k, если оно порождает одноцикловую перестановку на Xk. Отображение / транзитивно, если оно транзитивно на Xk для любого натурального k. Транзитивные отображения представляют значительный интерес в силу того, что применяются для решения как теоретических, так и практических задач. В частности, описаны семейства транзитивных автоматных отображений [1]. Будем называть состоянием с потерей [2] такое состояние s, что Л^^) = для некоторых xi,x2 e X, xi = x2. Теорема 1 [3]. Автоматное отображение /as : X * ^ X* биективно на Xk тогда и только тогда, когда автомат As не содержит состояний с потерей, достижимых из s за k шагов. Далее будем рассматривать только инициальные автоматы, порождающие биективные отображения. Следовательно, отображение /as осуществляет перестановку множества X, которую будем обозначать as. Действие инициального конечного автомата на входные последовательности можно описать с помощью бесконечного сбалансированного дерева [4]. Обозначим дерево, ассоциированное с действием автомата As, символом T(As). Обозначим через T(As, k) мультимножество состояний автомата A, где состояние s' входит в T(As, k) ровно столько раз, со сколькими вершинами k-го яруса T(As) ассоциировано состояние s'. Рассмотрим итерацию слова w e Xk автоматным отображением /as . Пусть /As(w) = w1, /As(/As(w)) = w2, ..., /AS(w) = w и m - наименьшее из возможных. Составим кортеж из перестановок ... ) и обозначим через Ar(T(As), w). Лемма 1. Автоматное отображение /as действует транзитивно на словах длины (k + 1), где k e N, тогда и только тогда, когда одновременно выполняются следующие условия: 1) /as действует транзитивно на словах длины k; 2) для всех w e Xk композиция о a^(s,w1) о ... о k-1) элементов Ar(T(As),w) является одноцикловой перестановкой. Заметим, что для каждого простого p существует циклическая группа перестановок (a+(p)), где ff+(p) = (0 1 ... (p - 1)) - образующий элемент группы [5]. Инициальные автоматы, где с каждым состоянием связана перестановка из (ст+(р)), образуют группу ASp [6]. Важным является тот факт, что (ст+(р)) -абелева группа. Тут и далее под автоматом будем понимать автомат из группы ASp. Пусть автомат As действует транзитивно на словах длины k. Следовательно, Ar(T(As),w) является некоторым упорядочиванием мультимножества перестановок, ассоциированных с состояниями из T(As,k). Более того, в силу коммутативности перестановок из (o+(p)), композиции элементов из Ar(T(As), w) совпадают для всех возможных w, т.е. композиция элементов Ar(T(As),w) однозначно определяется мультимножеством T(As, k) и не зависит от выбора w. Следовательно, достаточно проверить, что композиция перестановок (в произвольном порядке), ассоциированных с состояниями из T(As, k), является одноцикловой. Введём матрицы M и M, а также векторы V^ и R. По таблице переходов конечного автомата A построим матрицу смежности M размера n х n. Значения элементов матрицы M вычисляются как мощности множеств {x : x Е X, ^(si,x) = Sj}, где i,j - номера строки и столбца матрицы. Таким образом, i-я строка матрицы Mk описывает T (А5г ,k). Построим вектор V^ следующим образом. Как отмечено выше, с состоянием si автомата связана некоторая перестановка т из (a+(p)). Следовательно, в силу цикличности группы (a+(p)), т = a+(p)hi, hi = 0,... , (p - 1). Сопоставим i-му элементу вектора V-число hi. Положим R. = Mk • V^, где i-й элемент есть степень перестановки a+(p), получаемой при композиции перестановок, ассоциированных с T(Asi, k). Таким образом, задача проверки транзитивности сводится к последовательному сравнению с нулём значений i-х ячеек Rk, k ^ 1. Основной проблемой использования матрицы M является то, что количество попарно различных матриц Mk, k Е N, бесконечно. Построим матрицу M из M следующим образом. Каждому элементу mij матрицы M сопоставим элемент m^ = mij mod p матрицы M. Лемма 2. Пусть Rk = Mk • VT. Тогда rk = fk (mod p). Заметим, что количество различных матриц M для фиксированных p и n конечно и равно pn . Составим на основе представленных результатов алгоритм проверки транзитивности автомата As. (алгоритм 1). Можно показать, что строки матрицы Mk не могут быть произвольными, а лишь такими, где сумма элементов строки кратна p. Алгоритм 1. Алгоритм проверки транзитивности автомата Вход: Конечный автомат Asi Е ASp Выход: true, если Asi транзитивен, false иначе 1 2 3 4 5 6 7 8 9 Построить матрицу M и вектор V^ по автомату As.. Если i-й элемент V^ равен нулю, то вернуть false. Положить k := 1, L := 0. Пока Mk Е L Rk := Mk • VCTT. Если i-й элемент Rk сравним с 0 по модулю p, то вернуть false. Добавить Mk в L, увеличить k на 1. Вернуть true. 10 Теорема 2. Максимальное число умножений матриц, требуемое для остановки алгоритма, ограничено сверху числом (p(n-1) - 1). Полученная в теореме 2 оценка сложности является достижимой, что было подтверждено численными экспериментами.

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