О каркасе автомат

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ние собственных значений из спектра графа и спектров его подграфов. Этот подход позволяет рассмотреть вопрос поиска полного инварианта для классов графов, используя алгебраические свойства матриц, представляющих графы, и допускает обобщения на более широкие классы графов. Вариант такого обобщения также рассматривается в работе.
ЛИТЕРАТУРА
1. Balasubramanian K., Parthasarathy K. R. In search of a complete invariant for graphs // Lect. Notes Mathem. 1981. V. 885. P. 42−59.
2. Lindell S. A Logspace Algorithm for Tree Canonization // Proc. of the 24th Annual ACM Symposium on the Theory of Computing. New York: ACM, 1992. P. 400−404.
3. DattaS., LimayeN., Nimbhorkar P., Thierauf T., Wagner F. Planar Graph Isomorphism is in Log-Space // 24th Annual IEEE Conference on Computational Complexity. Paris, France, July 15 — July 18, 2009. ISBN: 978−0-7695−3717−7.
УДК 519. 17
О КАРКАСЕ АВТОМАТА
В. Н. Салий
В [1] было введено понятие каркаса автомата. Это упорядоченное множество, которое образуют слои автомата вместе с отношением обратной достижимости. Оно сыграло весьма существенную роль в описании автоматов, у которых каждая конгруэнция является ядром подходящего эндоморфизма. В работе устанавливаются некоторые свойства каркаса, связанные с основными алгебраическими конструкциями для автоматов, такими, как подавтомат, гомоморфизм, конгруэнция.
Автомат — это тройка A = (S, X, 5), где S и X — конечные непустые множества, соответственно множество состояний и множество входных сигналов, а 5: SxX ^ S — отображение, называемое функцией переходов.
Подмножество S'- C S называется устойчивым в автомате A, если 5(s, x) Е S'- для любых s Е S'- и x Е X. Если S'- устойчиво в A, то, ограничивая функцию переходов 5 на S'- x X, получают автомат A'- = (S'-, X, 5) -подавтомат автомата A, соответствующий S'-. Совокупность Sub A всех подавтоматов автомата A, упорядоченная отношением Ai ^ A2 Si C S2, где Ai = (Si, X, 5), i = 1, 2, является дистрибутивной
решеткой.
Пусть A = (S, X, 5) и B = (T, X, 5) — сравнимые автоматы, т. е. автоматы с одним и тем же множеством входных сигналов. Отображение: S ^ T по определению является гомоморфизмом автомата A в автомат B, если & lt-^(5(s, x)) = 5(& lt-^(s), x) для любых s Е S, x Е X. Взаимно однозначные гомоморфизмы автоматов называются вложениями, а их биективные гомоморфизмы — изоморфизмами. Эндоморфизмы автомата — это его гомоморфизмы в себя, автоморфизмы — изоморфизмы на себя.
Отношение эквивалентности в C S x S называется конгруэнцией автомата A = (S, X, 5), если оно согласовано с функцией переходов в том смысле, что (Vs, t Е S)(Vx Е X)((s, t) Е в =^ (5(s, x), 5(t, x)) Е в). Каждая конгруэнция в автомата A определяет его фактор-автомат A/в = (S/e, X, 5), где 5(e (s), x) := e (5(s, x)) для любых s Е S, x Е X.
Пусть X * -множество всех конечных слов над алфавитом X. Продолжим функцию переходов 5 на множество S x X*, полагая 5(s, e) = s, где e Е X* -пустое слово, и 5(s, px) = 5(5(s, p), x) для любых s Е S, x Е X, p Е X*. Говорят, что состояние t
достижимо в автомате A из состояния s, если найдется входное слово p Є X*, такое, что $(s, p) = t. Записывая это в виде (s, t) Є т, вводим отношение достижимости т в автомате A.
Симметричная часть, а = т П т-1 отношения достижимости называется отношением взаимной достижимости в A. Классы этой эквивалентности называют слоями автомата A. Каркасом автомата A назовем упорядоченное множество F (A) = (S/а, т-1). Его элементами являются слои автомата A, а порядком — отношение, обратное достижимости, перенесенное на слои: (a (t), a (s)) Є т-1 равносильно тому, что (s, t) Є т.
Теорема 1. Каждое конечное упорядоченное множество изоморфно каркасу подходящего автомата с двумя входными сигналами.
Теорема 2. Конечное упорядоченное множество тогда и только тогда изоморфно каркасу автономного автомата, когда у каждого его элемента имеется не более чем один нижний сосед.
Теорема 3. Если A и B — произвольные автоматы, то SubA = SubB тогда и только тогда, когда F (A) = F (B).
Теорема 4. Если ^ - вложение автомата A в автомат B и F (A) = F (B), то ^ - изоморфизм A на B.
Следствие 1. Если A- - подавтомат автомата A и F (A-) = F (A), то A- = A.
Следствие 2. Если ^ - эндоморфизм автомата A и F (& lt-^(A)) = F (A), то ^ - автоморфизм.
Теорема 5. Если 9 — конгруэнция автомата A, то F (A/9) = F (A) тогда и только тогда, когда 9 С а.
ЛИТЕРАТУРА
1. Салий В. Н. Автоматы, у которых все конгруэнции — внутренние // Изв. вузов. Математика. 2009. № 9. С. 36−45.
УДК 519. 5
КЛАССЫ ГРАФОВ, ВОССТАНАВЛИВАЕМЫЕ С ЛИНЕЙНОЙ ВРЕМЕННОЙ СЛОЖНОСТЬЮ
Е. А. Татаринов
Рассматривается задача [1] восстановления конечного связного неориентированного графа G без петель и кратных ребер при помощи агента, который премещается по ребрам графа G, считывает и изменяет метки на вершинах и инциденторах. На основе собранной информации агент строит граф H, изоморфный графу G с точностью до меток на вершинах и инциденторах графов. Необходимо найти метод обхода и разметки графа G с целью его восстановления.
Известен ряд методов восстановления графа [2, 3], которые используют не более четырех различных красок, однако имеют верхнюю оценку временной сложности восстановления, равную квадратичной и кубической функцией от числа вершин в восстанавливаемом графе соответственно. Для каждого метода нижней оценкой временной сложности восстановления является линейная функция от числа вершин в графе G. Данная работа посвящена выделению классов графов, для которых верхняя

ПоказатьСвернуть
Заполнить форму текущей работой