RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Труды ИСП РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Труды ИСП РАН, 2015, том 27, выпуск 1, страницы 51–68 (Mi tisp113)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

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

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

Институт системного программирования РАН

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

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

DOI: https://doi.org/10.15514/ISPRAS-2015-27(1)-4

Полный текст: PDF файл (266 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья

Образец цитирования: Игорь Бурдонов, Александр Косачев, “Обход неизвестного графа коллективом автоматов. Недетерминированный случай”, Труды ИСП РАН, 27:1 (2015), 51–68

Цитирование в формате AMSBIB
\RBibitem{BurKos15}
\by Игорь~Бурдонов, Александр~Косачев
\paper Обход неизвестного графа коллективом автоматов. Недетерминированный случай
\jour Труды ИСП РАН
\yr 2015
\vol 27
\issue 1
\pages 51--68
\mathnet{http://mi.mathnet.ru/tisp113}
\crossref{https://doi.org/10.15514/ISPRAS-2015-27(1)-4}
\elib{http://elibrary.ru/item.asp?id=23420341}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/tisp113
  • http://mi.mathnet.ru/rus/tisp/v27/i1/p51

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. И. Б. Бурдонов, А. С. Косачев, “Общий подход к решению задач на графах коллективом автоматов”, Труды ИСП РАН, 29:2 (2017), 27–76  mathnet  crossref  elib
  • Труды института системного программирования РАН
    Просмотров:
    Эта страница:85
    Полный текст:30
    Литература:14
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020