Автомати, які пересуваються по графах, є математичною формалізацією автономних мобільних агентів з обмеженою пам'яттю, що функціонують у дискретних середовищах. В межах цієї моделі виникла та інтенсивно розвивається велика область досліджень поведінки автоматів в лабіринтах (лабіринти є орієнтованими графами спеціального виду, які укладено на двовимірній цілочисловій решітці). Дослідження з цього напрямку одержали великий спектр застосувань, наприклад, в задачах аналізу зображень і навігації мобільних роботів. Автомати, що функціонують у лабіринтах, можуть розрізняти напрямки, тобто вони мають компас. У даній роботі розглянуто вершинну розмітку графа квадратної решітки, завдяки якій скінчений автомат без компаса може пересуватися по графі у довільному напрямку. Автомат одержує на свій вхід позначки усіх вершин із замкненого околу поточної вершини та пересувається поміж суміжними вершинами, обираючи цільову вершину за її позначкою. У роботі запропоновано так звану мінімальну детерміновану прохідну розмітку, яка задовольняє шуканій властивості. Розмітка називається детермінованою, якщо усі вершини із замкненого околу будь-якої вершини графа мають різні позначки. Доведено, що мінімальна детермінована прохідна вершинна розмітка графу квадратної решітки потребує п'ять різних типів позначок. Також мінімальні детерміновані прохідні розмітки підграфів графу квадратної решітки, ступінь яких менше чотирьох. Основною задачею про автомати та лабіринти є задача про побудову скінченого автомата, який обходить заданий клас лабіринтів. Запропоновано умову, що автомат обходить нескінчений граф, якщо він відвідує будь-яку довільно обрану вершину графа за скінчений час. Доведено, що колектив, який складається з одного автомата та трьох каменів, обходить нескінчений граф квадратної решітки з заданою на ньому мінімальною детермінованою прохідною розміткою, а ніякий колектив з меншим числом каменів цього зробити не може. Каміння розглядається як автомати найпростішого виду, пересування яких цілком визначається іншими автоматами колективу. Результати стосовно обходу нескінченого позначеного графа квадратної решітки збігаються з результатами A. B. Анджана стосовно обходу нескінченого мозаїчного лабіринту без дірок. Таким чином граф квадратної решітки після побудови на ньому мінімальної детермінованої прохідної розмітки та фіксації двох пар протилежних напрямків стає аналогом нескінченого мозаїчного лабіринту без дірок.

 Наукова періодика України 

---

  Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"