On the Directional Movement of a Graph-Walking Automaton without a Compass on Square Grid Graph

Сергій Сапунов

Про Спрямоване Переміщення Графохідного Автомату без Компаса на Графі Квадратної Решітки

Автор(и)

Сергій Сапунов відділ теорії керуючих систем Інститут прикладної математики і механіки НАН України

Ключові слова:

граф квадратної решітки, графохідний автомат, вершинна розмітка, спрямоване переміщення

Анотація

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