О распознавании лабиринтов автоматами

Изучается проблема существования автоматов, распознающих некоторые прямоугольные лабиринты. Доказывается отсутствие распознающего автомата для простых прямоугольных лабиринтов, что не имеет места для мозаичных лабиринтов. Приведен пример бесконечного класса $\pi$-лабиринтов, который не распознается автоматом.