Сборники трудов ИСП РАН


Обход неизвестного графа коллективом автоматов.

Игорь Бурдонов, Александр Косачев.

Аннотация

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

Ключевые слова

исследование графа, обход графа, конечный автомат, расширенный автомат, взаимодействующие автоматы, параллельная обработка, распределенные системы, тестирование

Издание

Труды Института системного программирования РАН, том 26, вып. 2, 2014, стр. 43-86.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2014-26(2)-2

Полный текст статьи в формате pdf Вернуться к содержанию тома