RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 1981 Volume 17, Issue 4, Pages 98–112 (Mi ppi1422)

This article is cited in 1 paper

Automata Theory and Large System Science

Team of Automata with Universal Passability

G. L. Kurdyumov


Abstract: Consider an integer-valued plane part of whose points are obstacles, while finite automata may be situated (and move about) at the remaining free points. The total number of automata on the plane is finite; each of these automata, at any free point, “knows” the direction toward point $(0, 0)$ (to within $90^{\circ}$), and also the presence and state of other automata at the same point. It is shown that there exists a team of four automata such that, if the automata are initially situated at any point $(i_0,j_0)$ such that there exists a path from $(i_0,j_0)$ to $(0,0)$, all automata will arrive at $(0,0)$. No single automaton with this property exists.

UDC: 62-507:621.391.1

Received: 30.07.1979
Revised: 30.01.1981


 English version:
Problems of Information Transmission, 1981, 17:4, 286–297

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024