Автор: О. М. Копытова
Источник: Материалы ХІ международной научно–практической конференции Математическое и программное обеспечение интеллектуальных систем (MPZIS–2013)
. Днепропетровск, 20–22 ноября 2013. ссылка
В работе продолжается изучение автоматов, устойчивых по поведению к локальной операции – переброске дуг. Под автоматом [1] понимается приведенный автомат Мили A = (S, Х, Y,δ,λ), где S, Х, Y – множества состояний, входных и выходных символов соответственно, а δ, λ – функции переходов и выходов. Если Х = {x}, т. е. x – единственный входной символ, то автомат называется автономным. Пусть е = (s, x′, y′, s1) – дуга в графе переходов автомата А. Переброской дуги е в состояние s2, отличное от s1, называем замену этой дуги на дугу (s, x′, y′, s2). Пусть автомат А′ получен из автомата А переброской некоторого множества его дуг. Если при этом автомат А′ остается изоморфным исходному автомату A, то говорим, что переброска сохраняет изоморфизм. Задача заключается в том, чтобы исследовать структуру циклов в автомате и найти условия, при которых существуют переброски, сохраняющие изоморфизм.
В [1] доказано, что переброска одной дуги в любом приведенном автомате всегда приводит к неизоморфному автомату. В [2] приведены структуры не сильно связных автоматов, в которых возможна переброска k дуг при любом k > 1. В [3] показано, что существуют сильно связные автоматы и переброски, сохраняющие изоморфизм, однако пока не удалось построить автомат с двумя такими перебросками. В дальнейшем, если не оговорено противное, под автоматом понимается автономный автомат. Неопределяемые понятия можно найти в [1].
Утверждение 1. Для любого автономного сильно связного приведенного автомата не существует переброски 2–х дуг, сохраняющей изоморфизм.
Утверждение 2. Для любого автономного не сильно связного приведенного автомата, представляющего собой несколько сильно связных компонент, не существует переброски 2–х дуг, сохраняющей изоморфизм.
Утверждение 3. Существует автономный не сильно связный приведенный автомат, допускающий переброску 2–х дуг, сохраняющую изоморфизм.
Эти утверждения основаны на том факте, что в общем случае граф переходов автономного автомата представляет собой набор компонент связности, причем каждая компонента является циклом с входящими в него деревьями. Если автомат сильно связен, то его граф переходов превращается в простой цикл. С другой стороны, цикл можно рассматривать как автономный групповой автомат, т. е. автомат, у которого {δ(s,x)|s∈S}=S.
Утверждение 4. Пусть А – автономный групповой автомат с n состояниями. Тогда:
1) при n≥3 в автомате А существует переброска k дуг, сохраняющая изоморфизм, для всех 3≤k≤n;
2) при n≤2 в автомате А не существует переброски k дуг, сохраняющей изоморфизм, где 1≤k≤2.
Заметим, что утверждения, аналогичные утверждениям 1 и 2, справедливы и для циклических орграфов без отметок на дугах.
Литература
Дискретные модели в теории управляющих систем. Москва: Макс–Пресс, 2009, с. 155–159.
Информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2013)(24.04 – 25.04.2013). Донецк: ДонНТУ, 2013. – с. 479–484.