В последние десятилетия все большее внимание привлекает тематика, связанная с автоматным анализом геометрических сред, изображений, графов, формальных языков и других дискретных структур. Одна из основных проблем этого направления теории автоматов — нахождение выхода из лабиринта. Основная проблематика для автоматов в лабиринтах группируется вокруг задач синтеза и анализа. Задача синтеза состоит в описании тех автоматов и коллективов автоматов, которые обходят лабиринты из заданного класса. Задача анализа состоит в описании по заданному автомату или коллективу автоматов всех лабиринтов или всех лабиринтов определенного вида, которые обходятся этими автоматами. В качестве главной модели выступают конечные автоматы в конечных плоских мозаичных и бесконечных плоских мозаичных лабиринтах. Данная статья является развитием основных положений предыдущей раработы авторов 1992 года. Здесь нашли отражение как новые результаты, так и уточнение ситуаций, описанных ранее. В первых двух разделах даются основные понятия, связанные с данной тематикой и с приводимыми здесь результатами. В последнем разделе подробно рассматривается случай поведения независимых систем конечных автоматов в указанных классах лабиринтов и в некоторых их обобщениях.

теория автоматов, теория графов, гиперграф, система автоматов, нахождение выхода из лабиринта

Математические вопросы и теория численных методов