Поведение конечных автоматов в лабиринтах

Работа посвящена исследованию задач о поведении конечных автоматов в лабиринтах. Для любого n строится лабиринт, который можно обойти с помощью 2n камней но нельзя обойти с помощью n камней. Спектр задач обхода обширен и затрагивает ключевые аспекты теоретической Computer Science. Конечно, решение таких задач не означает автоматическое решение сложных проблем теории сложности, тем не менее рассмотрение данных вопросов может положительно сказаться на понимании сути теоретической Computer Science. Есть надежда, что поведение автоматов в лабиринтах является хорошей моделью для нетривиальных теоретико-информационных задач, и отработка методов и подходов к исследованию поведения роботов даст более серьезные результаты с будущем. Задачи связанные c автоматным анализом геометрических сред имеют довольно богатую историю изучения. Первой работой, давшей начало подобного рода задачам, стоит признать работу Шеннона [24]. В ней рассматривается модель мыши в виде автомата, которая должна найти определенную цель в лабиринте. Другая ранняя работа, так или иначе затрагивающая нашу проблематику, это работа Фишера [9] о вычислительных системах с внешней памятью в виде дискретной плоскости. Серьёзным толчком к исследование поведения автоматов в лабиринтах послужила работы Деппа [7, 8], в которых предложена следующая модель: имеется некоторая конфигурация клеток из Z^2 (шахматный лабиринт), в которой конечные автоматы, обозревая некоторую окрестность клетки, в которой они находятся, могут перемещаться в соседнюю клетку в одном из четырёх направлений. Основной вопрос, который ставится в подобной модели, существует ли автомат обходящий все подобные лабиринты. В [20] Мюллер построил для заданного автомата плоскую ловушку (лабиринт который обходится не полностью) в виде 3-графа. Будах [5] построил шахматную ловушку для любого заданного конечного автомата. Отметим, что решение Будаха было довольно сложным (первые варианты содержали 175 страниц). Более наглядные решения данного вопроса представлены здесь [29, 31, 33, 34]. Антельман [2] оценил сложность подобной ловушки по числу клеток, а в [1] Антельман, Будах и Роллик сделали конечную ловушку для любой конечной системы автоматов. В постановке с шахматным лабиринтом и одним автоматом есть ещё ряд результатов, связанных с проблемами обходимости лабиринтов с различными числом дыр, с расслоениями лабиринтов по количеству состояний автомата и другими вопросами. Обзор подобных проблем можно найти например здесь [35]. Невозможность обхода всех плоских шахматных лабиринтов одним автоматом выдвинула вопрос об изучении возможных усилений модели автомата, которая решит задачу обхода. Основным способом усиления может являться рассмотрение коллектива автоматов,вместо одного автомата, взаимодействующих между собой. Частным и широко используемым случаем является рассмотрение системы из одного полноценного автомата и некоторого количества автоматов камней, которые не имеют внутреннего состояние и могут передвигаться только совместно с главным автоматом. Взаимодействие между автоматами является ключевой особенностью данного усиления, оно позволяется иметь коллективу (или одному автомату с камнями) внешнюю память, тем самым существенно разнообразит его поведение. Если от взаимодействия автоматов избавиться, то полученная независимая система будет немногим лучше одного автомата. Далее обсудим известные результаты связанные с коллективом автоматов.

обход лабиринта, конечный автомат

1. Antelmann H., Budach L., Rollik H. A. On universale traps // EIK. 1979. Vol. 15. No. 3. Pp. 123–131.

2. Antelmann H. An application of the prime number theorem in automata theory // ICS PAS Reports 411. 1980. Pp. 9–11.

3. Blum M., Kozen D. On the power of the compass // Proc. 19th IEEE FOCS Conf. 1978. Pp. 132–142.

4. Blum M., Sakoda W. On the capability of finite automata in 2 and 3 dimensional space // Proc. 17th IEEE FOCS Conf. 1977. Pp. 147–161.

5. Budach L. Automata and labyrinths // Math. Nachrichten 86. 1978. Pp. 195–282.

6. Burnside W., “On an unsettled question in the theory of discontinuous groups” // Quart. J. Pure Appl. Math., 1902, 33, 230–238.

7. Dopp K. Automaten in Labyrinthen I // EIK. 1971. Vol. 7. No. 2. Pp. 79–94.

8. Dopp K. Automaten in Labyrinthen II // EIK. 1971. Vol. 7. No. 3. Pp. 167–190.

9. Fischer P. C. Multi-tape and infinite-state automata: A survey // Comm. ACM. 1965. Vol. 8. No. 12. Pp. 799–805.

10. Habasinski Z., Karpinski M. A codification of Blum-Sakoda 7-pebbles algorithm // ICS PAS Reports 448. Warszawa, 1981.

11. Hall M. jun., “Solution of the Burnside problem for exponentsix” // Illinois J. Math., 1958, 2, 764–786.

12. Hemmerling A. 1-pointer automata searching finite plane graphs // Z. Math. Logik Grundlag. Math. 1986. Vol. 32. Pp. 245–256.

13. Hemmerling A. Normed two-plane traps for finite systems of cooperating compass automata // J. Inf. Process. Cybern. EIK 1987. Vol. 28. No. 8/9. Pp. 453–470.

14. Hoffmann F. One pebble does not suffice to search plane labyrinths // Lecture Notes in Computer Science. 1981. Vol. 117. Pp. 433–444.

15. Hoffman F. 1-Kiesel-Automaten in Labyrinthen // Report R-Math-06/82. AdW der DDR, Berlin, 1982.

16. Ivanov S. On the Burnside problem on periodic groups // Bull. Amer. Math. Soc. (N. S.), 27:2 (1992), 257–260; arXiv: math/9210221.

17. Kilibarda G. On the minimum universal collectives of automata for plane labyrinths // Discrete Math. Appl. 1993. Vol. 3. No. 6. Pp. 555–586.

18. Kriegel K. Universelle 1-Kiesel-Automaten fur k-komponentige Labyrinthe // Report R-Math-04/84. AdW der DDR, Berlin, 1984.

19. Minsky M. Computation: Finite and Infinite Machines (1st ed.). Englewood Cliffs, N. J.: Prentice-Hall, Inc, 1967.

20. Muler ? H. Endliche Automaten und Labyrinthen // EIK. 1971. Vol. 7. No. 4. Pp. 261–264.

21. Rollik H. A. Automaten in planaren Graphen // Acta Informatica. 1980. Vol. 13. Pp. 287–298.

22. Savitch W. Relations between nondeterministic and deterministic tape complexities // Journal of Computer and System Science. 1970. Vol. 4. Pp. 177–192.

23. Savitch W. Maze recognizing automata and nondeterministic tape complexity // Journal of Computer and System Science. 1973. Vol. 7. Pp. 389–403.

24. Shannon Cl. E. Presentation of a maze-solving machine // Cybernetics Trans. of the 8th Conf. of the Josiah Macy Jr. Found / Editor: H. Forester. 1951. Pp. 173–180.

25. Szepietowski A. A finite 5-pebble-automaton can search every maze // Information Processing Letters. 1982. Vol. 15. No. 5. Pp. 199–204.

26. Aдян С. И. Проблема Бернсайда и тождества в группах. М.: Наука, 1975.

27. Анджанс А. В. Поведение детерминированных и вероятностных автоматов в лабиринтах: Дис. ... канд. физ.-мат. наук. Рига, 1987. 90 с.

28. Голод Е. С. О ниль-алгебрах в финитно-аппроксимируемых группах // Изв. АН СССР. Сер. матем., 1964, 28(2), 273–276.

29. Килибарда Г. Об универсальных лабиринтах-ловушках для конечных множеств автоматов // Дискретная математика. 1990. Т. 2. Вып. 1. С. 72–79.

30. Килибарда Г. О минимальных универсальных коллективах автоматов для плоских лабиринтов // Дискретная математика. 1994. Т. 6. Вып. 4. C. 133–153.

31. Килибарда Г. Новое доказательство теоремы Будаха-Подколзина //

32. Килибарда Г., Ушчумлич Ш. О лабиринтах-ловушках для коллективов автоматов // Дискретная математика. 1993. Т. 5. Вып. 2. C. 29–50.

33. Кудрявцев В. Б., Подколзин А. С, Ушчумлич Ш. Введение в теорию абстрактных автоматов. М.: Изд-во МГУ, 1985.

34. Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. М.: Наука, 1985.

35. Кудрявцев Г. Килибарда Ш. Ушчумлич Системы автоматов в лабиринтах. Грант РФФИ № 06-01-00240.

36. Новиков П. С., Адян С. И. О бесконечных периодических группах. I, II, III // Изв. АН СССР. Сер. матем., 1968, 32(1), 212–244; 32(2), 251–524; 32(3), 709–731.

37. Санов И. Н. Решение проблемы Бернсайда для показателя 4 // Ученые записки ЛГУ. Сер. матем., 1940, 10, 166–170.

38. Xарари Ф. Теория графов. М.: Мир, 1973