Поведінка Безкомпасних Автоматів на Драбинних Графах

Анотація

Мета цієї публікації – дослідити можливості колективів безкомпасних автоматів у дослідженні драбинних графів. Кожен граф є анонімним, тобто вершини графа не мають ідентифікуючих позначок, і, таким чином, всі вершини одного степеня здаються автоматам ідентичними. Автомати не розрізняють вершини на основі їх координат або напрямку (це означає, що автомати не мають компаса). Розглядаються колективи, що складаються з керуючого автомата і декількох камінчиків, які є автоматами найпростішої форми, положення яких повністю визначаються керуючим автоматом. Представлено мінімальні колективи, які досліджують драбинні графи та деякі їх підграфи.