Multiprocessor automata. (English) Zbl 0653.68044

The notion of multiprocessor automata is introduced. The multiprocessor automaton may be thought of as the simplest model of parallel computations: there are more than one processors reading information from the tape simultaneously, and the switching function for each processor depends on the inner states of all processors on the step of computations. We prove some results on the hierarchies of two-way and one-way multiprocessor automata languages.


68Q45 Formal languages and automata
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: DOI


[1] Chrobak, M., Hierarchies of one-way multihead automata languages, (), 101-110 · Zbl 0571.68071
[2] Hartmanis, J., On non-determinancy in simple computing devices, Acta informatica, 1, 4, 336-344, (1972) · Zbl 0229.68014
[3] Inoue, K.; Takanami, I.; Nakamura, A.; Ae, T., One-way simple multihead finite automata, Theoret. comput. sci., 9, 311-328, (1979) · Zbl 0408.68050
[4] Nepomnyaschiy, V.A., Computations on Turing machines with labels, (), 47-48, (in Russian)
[5] Rosenberg, A.L., On multihead finite automata, (), 221-228
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.