\input zb-basic
\input zb-ioport
\iteman{io-port 00023771}
\itemau{Hromkovi\v{c}, Juraj; Inoue, Katsushi; Ito, Akira; Takanami, Itsuo}
\itemti{On the power of two-dimensional synchronized alternating finite automata.}
\itemso{Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 15, No.1, 90-98 (1991).}
\itemab
Two-dimensional synchronized finite automata are examined. These automata are the usual alternating finite automata working on rectangular two- dimensional tape and endowed with an additional mechanism enabling the synchronization of parallel processes. Intuitively, when a process enters a synchronizing state it can carry on its computation only if all other processes either stop in accepting states or enter synchronizing states with the same synchronizing symbol. The main result shows that synchronization enhances considerably the power of alternating two- dimensional finite alternating automata --- two-way, three-way and four- way two-dimensional synchronized finite automata have all the same power as rectangular array bounded automata defined by {\it K. Inoue} and {\it A. Nakamura} [Inf. Control 41, 305-323 (1979; Zbl 0411.68048)], which can be regarded as two-dimensional counterpart of linear bounded automata.
\itemrv{W.Zielonka (Bordeaux)}
\itemcc{}
\itemut{alternating finite automata; rectangular two-dimensional tape; synchronization of parallel processes}
\itemli{}
\end