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

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

---

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