Часть 2. Специальные вопросы теории интеллектуальных систем

Проблема типовой встречи для автоматов в лабиринтах

Г. Д. Килибарда

«МБ» университет

Аннотация: В статье рассматривается один специальный тип взаимодействия коллективов автоматов в лабиринтах. Для данного класса лабиринтов решается, относительно всех типов коллективов автоматов, следующая проблема: для каких пар типов существуют коллектив первого типа и коллектив второго типа такие, что если их в начальный момент поместить в любые две вершины любого лабиринта из данного класса лабиринтов, то они обязательно когда-то встретятся. Эту проблему называем проблемой типовой встречи (type meeting) для автоматов в данном классе лабиринтов. Здесь эта задача полностью решена как для случая класса всех конечных плоских мозаичных лабиринтов, так и для случая класса всех конечных плоских прямоугольных лабиринтов. В случае класса всех (конечных и бесконечных) плоских мозаичных лабиринтов для некоторых пар типов коллективов проблема типовой встречи пока остается открытой, а в случае класса всех плоских прямоугольных лабиринтов она все еще является полностью неисследованной.

Ключевые слова: коллектив автоматов, тип коллектива автоматов, плоский прямоугольный лабиринт, плоский мозаичный лабиринт, типовая встреча.