DOI: 10.17587/prin.7.559-567

УДК: 004.4

Исследование графов коллективом двигающихся автоматов

И. Б. Бурдонов, д-р физ.-мат. наук, вед. науч. сотр., e-mail: igor@ispras.ru, А. С. Косачев, канд. физ.-мат. наук, вед. науч. сотр., e-mail: kos@ispras.ru, Институт системного программирования РАН, Москва

Исследование графов автоматами является корневой задачей во многих приложениях. К таким приложениям относятся верификация и тестирование программных и аппаратных систем, а также исследование сетей, в том числе сети Интернет и GRID на основе формальных моделей. Модель системы или сети сводится к графу, свойства которого нужно исследовать. Настоящая публикация — вторая в серии трех статей, посвященных исследованию графов автоматами. Если в первой статье автомат был один, то в данной статье по дугам ориентированного графа двигаются несколько автоматов, обмениваясь сообщениями по независимой от графа сети связи. Такая постановка задачи оправдана тогда, когда исследование графа одним автоматом (компьютером) либо требует недопустимо большого времени, либо граф не помещается в памяти одного компьютера, либо и то и другое. Поэтому требуется параллельное и распределенное исследование графа коллективом автоматов. Изучается также возможность обхода недетерминированного графа.

Ключевые слова: ориентированный граф, упорядоченный граф, нумерованный граф, неизвестный граф, недетерминированный граф, обход графа, А-обход, автомат, робот, полуробот

Стр. 559–567