Определяющие соотношения для детерминированных графов
Gespeichert in:
| Veröffentlicht in: | Труды Института прикладной математики и механики НАН Украины |
|---|---|
| Datum: | 2008 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2008
|
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/20023 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Определяющие соотношения для детерминированных графов / А.С. Сенченко, Н.Н. Рубан // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 17. — С. 175-184. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-20023 |
|---|---|
| record_format |
dspace |
| spelling |
Сенченко, А.С. Рубан, Н.Н. 2011-05-20T08:02:19Z 2011-05-20T08:02:19Z 2008 Определяющие соотношения для детерминированных графов / А.С. Сенченко, Н.Н. Рубан // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 17. — С. 175-184. — Бібліогр.: 9 назв. — рос. 1683-4720 https://nasplib.isofts.kiev.ua/handle/123456789/20023 519.7 ru Інститут прикладної математики і механіки НАН України Труды Института прикладной математики и механики НАН Украины Определяющие соотношения для детерминированных графов Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Определяющие соотношения для детерминированных графов |
| spellingShingle |
Определяющие соотношения для детерминированных графов Сенченко, А.С. Рубан, Н.Н. |
| title_short |
Определяющие соотношения для детерминированных графов |
| title_full |
Определяющие соотношения для детерминированных графов |
| title_fullStr |
Определяющие соотношения для детерминированных графов |
| title_full_unstemmed |
Определяющие соотношения для детерминированных графов |
| title_sort |
определяющие соотношения для детерминированных графов |
| author |
Сенченко, А.С. Рубан, Н.Н. |
| author_facet |
Сенченко, А.С. Рубан, Н.Н. |
| publishDate |
2008 |
| language |
Russian |
| container_title |
Труды Института прикладной математики и механики НАН Украины |
| publisher |
Інститут прикладної математики і механіки НАН України |
| format |
Article |
| issn |
1683-4720 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/20023 |
| citation_txt |
Определяющие соотношения для детерминированных графов / А.С. Сенченко, Н.Н. Рубан // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2008. — Т. 17. — С. 175-184. — Бібліогр.: 9 назв. — рос. |
| work_keys_str_mv |
AT senčenkoas opredelâûŝiesootnošeniâdlâdeterminirovannyhgrafov AT rubannn opredelâûŝiesootnošeniâdlâdeterminirovannyhgrafov |
| first_indexed |
2025-11-27T02:41:28Z |
| last_indexed |
2025-11-27T02:41:28Z |
| _version_ |
1850794974001496064 |
| fulltext |
ISSN 1683-4720 Труды ИПММ НАН Украины. 2008. Том 17
УДК 519.7
c©2008. А.С. Сенченко, Н.Н. Рубан
ОПРЕДЕЛЯЮЩИЕ СООТНОШЕНИЯ ДЛЯ
ДЕТЕРМИНИРОВАННЫХ ГРАФОВ
В работе предлагается задание детерминированных инициальных графов с помощью определяю-
щей пары, которая является аналогом системы определяющих соотношений для автомата. Найдена
минимальная определяющая пара и предложена процедура перехода от произвольной определяю-
щей пары к соответствующей ей минимальной.
Введение. Известно, что многие объекты дискретной математики и алгебры
можно представить определяющими соотношениями. Так в 1882 году В.Фон Дик
предложил задавать группы посредством порождающих элементов и определяющих
соотношений [1]. Впоследствии было предложено аналогичное задание полугрупп.
В связи с таким заданием вышеперечисленных объектов возникли знаменитые
проблемы Туэ-Дэна [2], самой сложной из которых является проблема изоморфиз-
ма: две полугруппы/группы заданы системой определяющих соотношений (СОС);
необходимо найти алгоритм, позволяющий по СОС определить, изоморфны ли по-
лугруппы/группы друг другу или нет.
В 1947 году была доказана неразрешимость проблем Туэ-Дэна: А.А.Марковым
и Эм.Постом для полугрупп [3], а чуть позднее в 1955 году П.С.Новиков и У.Бун
доказали неразрешимость для групп.
В 1961 Ю.И.Соркин в работе [4] сформулировал и предложил позитивное кон-
структивное решение проблем Туэ-Дэна для детерминированных всюдуопределен-
ных автоматов. Тем самым была показана принципиальная возможность исполь-
зования СОС для решения задач теории автоматов. В дальнейшем идеи Соркина
обобщаются и используются для исследования проблем теории экспериментов с ко-
нечными автоматами и лабиринтами.
В частности, в работе [5] предложен частный случай решения проблемы изомор-
физма всюдуопределенных автоматов без непосредственного построения автоматов
по их системе определяющих соотношений, а в работе [6] аналогичным образом ре-
шена проблема для частичных автоматов.
В связи с определенной схожестью структуры графов и автоматов возникает
идея распространить результаты А.С.Сенченко на графы. Наиболее схожи по струк-
туре с автоматами, на наш взгляд, являются графы с детерминированной раскрас-
кой (детерминированные графы), впервые рассмотренные С.В.Сапуновым в [7].
1. Основные определения.
Определение. Под автоматом понимается конечный детерминированный ини-
циальный, инициально-связный частичный автомат без выхода [8]. Будем считать,
что A = (A,X, δ, a0) – автомат, у которого A – конечное множество состояний, a0
– начальное состояние, δ : A ×X → A – функция переходов. Множество всех слов
175
А.С. Сенченко, Н.Н. Рубан
конечной длины в алфавите X обозначается X∗. Пусть p = x1 . . . xk – произволь-
ное слово в алфавите X. Слово xk . . . x1 будем обозначать через p−1. Длина слова p
обозначается d(p) и d(p) = k. Пустое слово множества X∗ обозначим через λ.
Одним из известных способов задания автоматов является его представление
определяющими соотношениями, то есть такими парами слов (p, q), что a0p и a0q
определяют одно и то же состояние. Множество таких определяющих соотноше-
ний, однозначно задающих автомат, называется его системой определяющих соот-
ношений. Для частичных автоматов в работе [6] была введена модификация СОС,
названная определяющей системой, которая состоит из двух компонент {ρ,M}. Пер-
вая ее компонента ρ, состоящая из таких пар слов (p, q), что a0p, a0q определены и
a0p = a0q является аналогом СОС и однозначно задает базу [4] автомата. Вторая
компонента M состоит из таких слов px (x ∈ X), что a0p определено, а a0px не опре-
делено. Она однозначно выделяет автомат от других подобных ему по свободному
расширению [4]. В работах [9], [5], [6] были решены задачи, связанные с представ-
лением автоматов определяющими соотношениями: найдена минимальная СОС для
автомата; найдено преобразование (редукция) СОС, позволяющее определить соот-
ветствует ли данная СОС данному автомату; соответствуют ли две данные СОС
одному и тому же автомату. Для распространения этих результатов на схожие по
структуре объекты с автоматами – детерминированные графы необходимо ввести
на них аналог СОС.
Пусть G = (G, E, C, ψ, g0) – конечный, простой неориентированный граф с от-
метками вершин, у которого G – множество вершин, E – множество ребер, C –
множество отметок вершин, ψ : G → C – функция отметок, g0 – инициальная вер-
шина. Окрестностью вершины O(g) называется вершина g вместе с множеством всех
вершин, смежных с ней: O(g) = {g} ∪ E {g}. Граф G = (G,E, C, ψ, g0) называется
детерминированным [7], если у любых двух различных вершин из любой окрестно-
сти отметки различны, то есть ∀g ∈ G, u, v ∈ O(g) из u 6= v следует ψ(u) 6= ψ(v).
Путем в детерминированном графе G = (G,E, C, ψ, g0) будем называть произволь-
ную последовательность отметок вершин p = ψ(g1) . . . ψ(gk), где (gi, gi+1) ∈ E, для
всех 1 ≤ i < k. Если в окрестности вершин v нет вершины с отметкой c, то будем
говорить, что путь по c из v не определен, в противном случае путь определен. В
работе рассматриваются только связные графы.
Пусть G = (G,E,C, ψ, g0) детерминированный граф. Удалим из G все висячие
вершин, отличные от инициальной g0. Будем повторять данную операцию до тех
пор, пока это возможно. Получившийся граф назовем базой графа G. Опишем вер-
шины, входящие в базу графа. База может состоять из одной инициальной вершины,
если граф является деревом. Если же граф не дерево, то в базу входят только те вер-
шины, через которые проходит некоторый простой цикл и вершины, через которые
проходит простой путь от начальной вершины к некоторому простому циклу.
2. Определяющие слова для детерминированных графов. Пусть {S,L}
пара конечных множеств слов таких, что для любого слова p из множества S вы-
полняется равенство g0p = g0, а для любого слова qc ∈ M , где c ∈ C путь g0q
определен, а путь g0qc не определен. Рассмотрим процедуру построения графа по
176
паре множеств {S, L}:
1) Строим циклы по словам множества S и в любом случае получаем граф с
раскрашенными вершинами, причем детерминированность раскраски не обязатель-
но выполняется.
2) Осуществляется детерминизация полученного графа путем отождествления
вершин с одинаковой раскраской из каждой окрестности. Ввиду конечности множе-
ства S данная операция выполняется конечное число раз и результат однозначен.
3) К полученному графу, используя элементы множества L, добавляем необ-
ходимые "тупиковые" ветки, если таковые есть. При необходимости осуществляем
повторную детерминизацию.
Пару {S, L} назовем определяющей для детерминированного графа G, если она
однозначно его задает. Определяющая пара является аналогом определяющей си-
стемы для частичных автоматов, рассмотренных в [6]. Проиллюстрируем ход вы-
полнения вышеуказанной процедуры на следующем примере.
Пример 1.
Пусть S = {abcdba; abdcbcba} и L = {ac; ad; abdcad; abcdab; abcab; abcdacb;
abdacd}, тогда в ходе выполнения процедуры последовательно получаем графы, по-
лученные на рисунке 1.
Рис. 1. Пример детерминизации графа
Детерминизацию можно осуществлять один раз, то есть шаг 2 выполнять по-
сле шага 3, но, на наш взгляд, лучше ее проводить после анализа каждого слова
множеств S и L.
Не всякая пара множеств {S, L} задает граф, потому что вершина соответству-
ющая некоторому слову множества L, может быть не висячей. Приведем пример
таких множеств S и L, которые не являются определяющими ни для какого графа.
Пример 2.
Пусть S = {abcdba; abdcbcba} и L = {ac; ad; abdcad; abcdab; abcab; abcdacb;
abdacd; abdaba}, тогда шаги 1 и 2 приведут к аналогичному результату, первые семь
слов множества L строят граф такой же, как и в предыдущем примере, а вершина,
соответствующая последнему слову (она выделена на рисунке 2) – не содержит в
своей окрестности вершины с меткой b, поскольку в L содержится слово abcdab, а
177
А.С. Сенченко, Н.Н. Рубан
abcda является путем к выделенной вершине.
Рис. 2. Этапы построения графа по паре {S, L}
В дальнейшем предполагается формализировать условия для множеств S и L,
для которых пара {S, L} является определяющими словами для некоторого детер-
минированного графа.
3. Построение по графу его определяющей пары. Покажем, что каждый
детерминированный граф имеет хотя бы одну определяющую пару.
Пусть C = {c1, ..., cm} и c1 ≤ c2 ≤ . . . ≤ cm – произвольно зафиксированный
линейный порядок P на C. Введем линейный порядок ≤ на множестве C∗ всех слов
в алфавите C таким образом:
1) ci ≤ ci; 2) если d(p) < d(q), то p ≤ q; 3) c′1 . . . c′s = p ≤ q = c′′1 . . . c′′s , если c′k ≤ c′′k
для некоторого k ≤ s, в то время как c′1 = c′′1, . . . , c
′
k−1 = c′′k−1.
Другими словами слово меньшей длины предшествует слову большей длины, а
слова одинаковой длины сравниваются в соответствии с лексикографическим по-
рядком (по алфавиту). Очевидно, что порядок ≤ на C∗ однозначно определяется
некоторым порядком P на C.
Каждую вершину графа G именуем кратчайшим по введенному порядку ≤ сло-
вом, соответствующим ей, то есть строим кратчайший по порядку ≤ базис дости-
жимости. Полученное множество имен вершин обозначим через VG. Заметим, что
в силу минимальности имен вершин любой начальный отрезок любого слова из VG
тоже принадлежит базису достижимости VG.
Для всех слов p = p1c
′c ∈ VG и всех отметок c1, отличных от c и c′, если путь
p1c
′cc1 определен и соответствует вершине с именем q = q1c1 и p1c
′cc1 6= q1c1, то цик-
лическое слово p1c
′cc1q
−1
1 помещаем в множество Σ1. Если же соответствующий путь
p1c
′cc1 не определен, то слово p1c
′cc1 помещаем в множество ΛG. Затем в множестве
Σ1 из всех пар обратных слов p и p−1 оставляем одно кратчайшее по порядку ≤,
а другое исключаем. Получившееся множество обозначим через ΣG. Заметим, что
если слово p принадлежит ΣG, то для любого его начального отрезка p1 вершина,
соответствующая слову p1 содержится в базе графа G.
Теорема 1. Пара {ΣG,ΛG} является определяющей для графа G.
Доказательство. По паре {ΣG, ΛG} построим детерминированный граф G′. По-
178
кажем, что графы G и G′ изоморфны.
Пусть вершина g с именем p принадлежит базе графа G. Тогда по построению
ΣG в нем существует такое слово q, для которого p или p−1 является начальным
отрезком. Поэтому g принадлежит базе графа G′ и имя вершины g есть слово p.
Пусть вершина g принадлежит базе графа G′. Тогда либо через эту вершину
проходит некоторый простой цикл, либо через нее проходит путь к некоторому про-
стому циклу. Рассмотрим первый случай: пусть V ′
G – базис достижимости графа
G′ и p ∈ V ′
G – имя вершины g в этом базисе. Тогда существует такое слово q, что
g0p = g0pq. Поскольку pq /∈ V ′
G, то существует такой начальный отрезок wc слова
pq, что w ∈ V ′
G, а wc /∈ V ′
G. Пусть r – такое слово из базиса V ′
G, что g0r = g0wc. Тогда
по построению ΣG меньшее из слов wc(r)−1 и r(wc)−1 по порядку ≤ принадлежит
ΣG, следовательно, g принадлежит базе графа G и имя вершины g есть слово p.
Рассмотрим второй случай. Пусть p – имя вершины g в базисе V ′
G. Тогда суще-
ствуют такие слова q и z, что pz ∈ V ′
G и g0pz = g0pzq. Поскольку pzq /∈ V ′
G, то
существует такой начальный отрезок wc слова pzq, что w ∈ V ′
G, а wc /∈ V ′
G. Пусть r
– такое слово из базиса V ′
G, что g0r = g0wc. Тогда, так же как и в первом случае, по
построению ΣG меньшее из слов wc(r)−1 и r(wc)−1 по порядку ≤ принадлежит ΣG,
следовательно, g принадлежит базе графа G и имя вершины g есть слово p. Таким
образом доказано, что базы графов G и G′ совпадают.
Пусть теперь вершина g графа G не принадлежит его базе и пусть p ∈ VG – имя
вершины g. Тогда из конечности графа G следует, что существует такое слово q, что
pq ∈ ΛG, поэтому вершина g с именем p принадлежит графу G′ и не находится в его
базе. Обратно, пусть вершина g графа G′ не принадлежит его базе и p ∈ V ′
G – имя
вершины g. Тогда по построению графа G′ существует такое слово q, что pq ∈ ΛG,
следовательно, вершина g с именем p принадлежит графу G и не находится в его
базе. Таким образом показано, что графы G и G′ изоморфны. ¤
Определяющую пару {ΣG,ΛG} назовем канонической для G. Из минимальности
длин слов из базиса достижимости VG и минимальности циклических слов базиса
достижимости ΣG вытекает
Следствие 1. Каноническая определяющая пара {ΣG, ΛG} является минималь-
ной по длине слов определяющей парой для графа G.
Пример 3.
Для заданного на рисунке 3 графа канонической определяющей парой являются
ΣG = {abcdba} и ΛG = {ac; ad; abcab; abcad; abdab; abdacb; abdacd}.
4. Редукция определяющей пары. В работах [6], [9] для частичных авто-
матов была решена задача характеризации определяющей системы для автомата.
Задача заключается в следующем: по заданной конечной системе {ρ,M} и заданно-
му автомату A определить, является ли система {ρ, M} определяющей для A. Эта
задача решена без построения автомата по {ρ,M} с дальнейшим его сравнением с
исходным автоматом, а с помощью преобразования (редукции) системы {ρ,M} и
дальнейшим сравнением результата редукции с канонической определяющей систе-
мой автомата A.
Рассмотрим решение этой задачи для детерминированных графов. Для этого нам
179
А.С. Сенченко, Н.Н. Рубан
Рис. 3. Детерминированный граф, для которого построена каноническая определяющая пара
необходимо модифицировать операции редукции к детерминированным графам.
Пусть {S, L} – определяющая пара для некоторого детерминированного графа
G и пусть p = p1xp2 – некоторое слово из множества S. Введем понятие разрыва
слова p: если p1x ≤ p−1
2 x по введенному выше порядку ≤, то разрывом слова p будет
пара слов (p1x, p−1
2 x); в противном случае разрывом p будет пара (p−1
2 x, p1x).
На множестве слов из обоих компонент пары {S, L} введем такие операции:
1) Пусть p1xixjxip2 – некоторое слово любого из множеств S и L. Это слово
заменим словом p1xjp2.
2) Пусть p ∈ S и p−1 ≤ p, тогда слово p заменяем словом p−1.
3) Пусть (p1x, p2x) – некоторый разрыв слова p ∈ S, тогда в множестве S слово
p2xq заменим словом p1xq, слово qxp−1
2 заменим словом qxp−1
1 , а в множестве L
слово p2xq заменим на p1xq.
4) Удалим из S и L повторяющиеся слова, оставляя по одному экземпляру.
Операции выполняются в циклическом порядке до тех пор, пока это возможно.
Результат редукции обозначим через < S, L >. Поскольку все операции не увели-
чивают количество и длину слов, и множества конечны, то процедура редукции
завершается после выполнения конечного числа шагов.
Эти операции являются модификацией операций редукции определяющей систе-
мы ρ,M для частичных автоматов [6]:
1′) Из ρ удаляются пары вида (p, p).
2′) В ρ каждая пара слов (p, q) заменяется парой (q, p) в случае, когда q ≤ p.
3′) Пусть (p1, p2) – некоторая пара из ρ. Тогда в ρ каждая пара вида (p2t, w)
заменяется на пару (p1t, w), а каждая пара вида (w, p2t) заменяется парой (w, p1t).
В множестве M каждое слово p2t заменяется словом p1t.
4′) Из ρ и M удаляются повторяющиеся элементы (пары и слова соответственно),
оставляя по одному экземпляру.
Несложно увидеть, что операции редукции для частичных автоматов (2′), (3′),
(4′) полностью соответствуют аналогичным операциям редукции детерминирован-
ных графов, а выполнение операции (1′) равносильно многократному выполнению
операции (1) конечное число раз.
180
Теорема 2. Пара {S,L} является определяющей для детерминированного графа
G тогда и только тогда, когда < S,L >= {ΣG, ΛG}.
Доказательство. Пусть < S,L >= {ΣG, ΛG}, т.е. пара < S,L > была преобразо-
вана в {ΣG, ΛG} посредством применения конечного числа операция редукций пары.
Поэтому, исходя из того, что {ΣG, ΛG} определяющая пара для G, то и < S, L > так-
же определяющая для G, так как применение любой из операций редукции к паре
не изменяет детерминированного графа, для которого пара является определяющей.
Таким образом, необходимость утверждения доказана.
Покажем достаточность утверждения. Пусть S,L – определяющая пара для де-
терминированного графа G. Покажем, что < S,L >= {ΣG,ΛG}. Каждому детер-
минированному графу G = (G,E, C, ψ, g0) однозначно соответствует некоторый ча-
стичный автомат A(G) = (G,C, δA, g0), у которого функция переходов δA однозначно
строится по множествам G,E и ψ таким образом: для всех ребер (g1, g2) ∈ E, у ко-
торых ψ(g1) = c1 и ψ(g2) = c2, δA(g1, c2) = g2 и δA(g2, c1) = g1. Если ψ(g′) = c′, то
δA(g′, c′) = g′. Если же в окрестности вершины g нет ни одной вершины с меткой c,
то переход δA(g, c) не определен.
Полученный таким образом частичный автомат своей структурой будет очень
схожим на исходный детерминированный граф: у автомата те же состояния, что
и вершины графа, а каждому ребру графа соответствует в автомате два перехода.
Кроме того, в автомате добавлены петли в каждом состоянии. Нам необходимо опи-
сать все эти переходы, используя тот факт, что пара {S,L} является определяющей
для графа G. Для этого выполним такие преобразования пары {S,L} в два множе-
ства ρ и M , причем ρ – множество пар слов в алфавите C, а M – множество слов в
алфавите C. Каждое слово p множества S имеет вид p = p′qp′, причем p′, q 6= λ. При
этом длина слова q либо 1, либо больше одного, причем во втором случае первая и
последняя буквы слова q различны.
Пусть d(q) = 1 и p = c1c2 . . . ckqck . . . c2c1, тогда в ρ поместим пары (c1, c1c2c1),
(c1c2, c1c2c3c2), . . ., (c1c2 . . . ck, c1c2 . . . ckqck). Кроме того, в ρ поместим пары, описы-
вающие петли автомата A(G): (c1, c1c1), (c1c2, c1c2c2), . . ., (c1c2 . . . ckq, c1c2 . . . ckqq).
Пусть длина слова q есть четное число (т.е. d(q) = 2w, p = c1c2 . . . ckc
′
1c
′
2 . . .
c′2w−1c
′
2wck . . . c2c1). Тогда, как и в предыдущем случае, в ρ поместим пары
(c1, c1c2c1), (c1c2, c1c2c3c2), . . ., (c1c2 . . . ck−1, c1c2 . . . ck−1ckck−1); пары
(c1c2 . . . ck, c1c2 . . . ckc
′
1ck), (c1c2 . . . ckc
′
1, c1c2 . . . ckc
′
1c
′
2c
′
1), . . ., (c1 . . . ckc
′
1 . . . c′w−1,
c1 . . . ckc
′
1 . . . c′w−1c
′
wc′w−1); пары (c1 . . . ck, c1 . . . ckc
′
2wck), (c1 . . . ckc
′
2w, c1 . . .
ckc
′
2wc′2w−1c
′
2w), . . ., (c1 . . . ckc
′
2wc′2w−1 . . . c′w+2, c1 . . . ckc
′
2wc′2w−1 . . . c′w+2c
′
w+1c
′
w+2) и, кро-
ме того, две такие "особые" пары (c1 . . . ckc
′
2wc′2w−1 . . . c′w+2c
′
w+1,
c1 . . . ckc
′
1c
′
2 . . . c′wc′w+1) и (c1 . . . ckc
′
1c
′
2 . . . c′w−1c
′
w, c1 . . . ckc
′
2wc′2w−1 . . . c′w+1c
′
w). После это-
го, как и в первом случае, в ρ добавляем пары, описывающие петли автомата A(G):
(c1, c1c1), (c1c2, c1c2c2), . . ., (c1c2 . . . ck, c1c2 . . . ckck), (c1c2 . . . ckc
′
1, c1c2 . . . ckc
′
1c
′
1), . . .
,(c1c2 . . . ckc
′
1 . . . c′w−1c
′
w, c1c2 . . . ckc
′
1 . . . c′w−1c
′
wc′w), (c1c2 . . . ckc
′
2w, c1c2 . . . ckc
′
2wc′2w), . . .,
(c1c2 . . . ckc
′
2wc′2w−1 . . . c′w+1, c1c2 . . . ckc
′
2wc′2w−1 . . . c′w+1c
′
w+1). Если же длина слова q
число нечётное (т.е. d(q) = 2w+1, p = c1c2 . . . ckc
′
1c
′
2 . . . c′2wc′2w+1ck . . . c2c1), то вместо
двух "особых" пар пишем одну такую пару (c1 . . . ckc
′
1c
′
2 . . . c′wc′w+1,
181
А.С. Сенченко, Н.Н. Рубан
c1 . . . ckc
′
2w+1c
′
2w . . . c′w+2c
′
w+1), а остальные пары записываем так же, как и в преды-
дущем случае.
Каждое слово p = c1 . . . ck−1ckz множества L помещаем в множество M и, кро-
ме того, как и в первом случае, в ρ добавляем пары (c1, c1c2c1), (c1c2, c1c2c3c2),
. . ., (c1c2 . . . ck−1, c1c2 . . . ck−1ckck−1) и пары, описывающие петли автомата A(G):
(c1, c1c1), (c1c2, c1c2c2), . . ., (c1c2 . . . ck, c1c2 . . . ckck).
После этого из всех слов множества M и всех слов во всех парах множества ρ
удалим начальный символ c1.
Объясним выполненные преобразования. Каждому слову множества S описы-
ваем некоторый маршрут в графе G. Каждому ребру из этого маршрута соот-
ветствует два перехода δA(G). Все эти переходы мы описываем парами (c1 . . . ci,
c1 . . . cici+1ci). Кроме того, если в графе G существует хоть один простой цикл, он
должен быть описан некоторыми словами множества S (вершины этого цикла имеют
отметки со штрихами, а концевая вершина имеет отметку ck). Тогда для описания
этого цикла в A(G) необходимо "соединить" ветви цикла в вершине, противопо-
ложной концевой (их одна или две, в зависимости от четности длины цикла). Это
происходит процессом добавления названных нами "особых" пар. Каждая неопре-
деленность функции переходов A(G) однозначно соответствует некоторому слову из
множества L. Таким образом, мы полностью описываем поведение функции пере-
ходов A(G) и значит ρ,M – однозначно задает автомат A(G), то есть является его
определяющей системой [6].
Рассмотрев правила построения канонической определяющей пары {ΣG, ΛG} для
графа G и канонической определяющей системы {κA(G),KA(G)} для автомата A(G),
несложно убедиться, что в результате выполнения показанного выше преобразова-
ния к {ΣG, ΛG}, получим систему {χ,H}, отличающуюся от {κA(G),KA(G)} возмож-
ными повторами одинаковых пар (в χ) или слов (в H).
В [6] показано, что результат редукции < ρ, M >= {κA(G),KA(G)}, поэтому <
S, L >= {ΣG,ΛG}. ¤
Проиллюстрируем результат выполнения процедуры редукции детерминирован-
ного графа на следующем примере.
Пример 4. Выполним редукцию пары {S, L} из примера 1.
S : abcdba
abcdba
(1)−→ abdcba
(2)−→ abcdba
(4)−→ удаляем
L : ac
ad
abdcad
(3; abdc→abc)−→ abcad
abcdab
(3; abcd→abd)−→ abdab
abcab
abcdacb
(3; abcd→abd)−→ abdab
abdacd
Получили, что результат редукции пары {S, L} совпадает с канонической опре-
182
деляющей парой {ΣG, ΛG}.
На рисунке 4 изображен автомат A(G), построенный по паре {S, L}. Выполним
преобразование пары {S, L} в множества ρ и M , как в доказательстве теоремы 2.
ρ : {(λ, ba), (b, bcb), (b, bdb), (bd, bcd), (bc, bdc), (λ, a), (b, bb), (bc, bcc), (bd, bdd),
(bd, bdcd), (bc, bcbc), (bcb, bdcb), (bdc, bcbc), (bdc, bdcc), (bcb, bcbb), (bdc, bdcac),
(bdca, bdcaa), (bc, bcdc), (bcd, bcdad), (bcd, bcdd), (bcda, bcdaa), (bca, bcaa),
(bcdac, bcdacc), (bcda, bcdaca), (bda, bdaa), (bdac, bdacc), (bda, bdaca)}
M : {c, d, bdcad, bcdab, bcab, bcdacb, bdacd}
Рис. 4. Иллюстрация к доказательству теоремы 2
Проведя редукцию системы ρ,M получаем такие результаты:
< ρ >: {(λ, ba), (b, bcb), (b, bdb), (bd, bcd), (bc, bdc), (λ, a), (b, bb), (bc, bcc), (bd, bdd),
(bc, dcac), (bd, bdad), (bca, bcaa), (bda, bdaa), (bdac, bdacc), (bda, bdaca)}
< M >: {c, d, bcad, bdab, bcab, bdacb, bdacd},
что совпадает с канонической определяющей системой автомата A(G).
Заключение. Таким образом, в настоящей работе предложено представление
детерминированных графов определяющей парой, которая является аналогом си-
стемы определяющих соотношений. Найдены процедура построения графа по его
определяющей паре, процедура построения минимальной (канонической) определя-
ющей пары для графа и процедура преобразования произвольной определяющей
пары графа к канонической. Полученные результаты являются распространением
соответствующих задач теории автоматов на графы и могут быть использованы при
проведении диагностических и контрольных экспериментов с детерминированными
графами.
1. Чандлер Б., Магнус В. Развитие комбинаторной теории групп. – М.: Мир, 1985. – 255с.
2. Адян С.И., Дурнев В.Г. Алгоритмические проблемы для групп и полугрупп // Успехи матема-
тических наук. – 2000. – т.55, вып.2. – C.3-94.
3. Лаллеман Ж. Полугруппы и комбинаторные приложения. – М.: Мир, 1985. – 440с.
4. Соркин Ю.И. Теория определяющих соотношений для автоматов // Проблемы кибернетики. –
1961. – вып.9. – C.45-69.
5. Грунский И.С., Сенченко А.С. Каноническая система определяющих соотношений для автома-
тов // Труды ИПММ НАН Украины. – 2002. – вып.7. – C.58-63.
6. Сенченко А.С. Свойства определяющих систем для частичных автоматов // Труды ИПММ
183
А.С. Сенченко, Н.Н. Рубан
НАН Украины. – 2003. – вып.8. – C.111-119.
7. Сапунов С.В. Эквивалентность отмеченных графов // Труды ИПММ НАН Украины. – 2002. –
вып.7. – C.162-167.
8. Богомолов А.М., Салий В.Н. Алгебраические основы теории дискретных систем. – М.: Наука,
1997. – 368с.
9. Сенченко А.С. Представление автоматов определяющими соотношениями их поведения: Дис.
. . . канд. физ.–мат. наук / К. Институт кибернетики им. В.М.Глушкова, 2005.
Славянский государственный педагогический ун-т
rubannn@gmail.com, senchenko@pisem.net
Получено 01.11.08
184
содержание
Том 17
Донецк, 2008
Основан в 1997г.
|