One-way cellular automata on Cayley graphs. (English) Zbl 0821.68087
Summary: The notion of one-dimensional one-way cellular automata has been introduced to model cellular automata with only a one-way communication between two neighbor cells. In this paper, we generalize this notion to cellular automata working on different communication graphs. We present some sufficient conditions for a cellular automaton to be stimulated by a one-way cellular automaton having the same underlying graph, and we give some bounds on the simulation-time of this mimic.
MSC:
| 68Q80 | Cellular automata (computational aspects) |
Keywords:
one-way cellular automataReferences:
| [1] | Bollobás, B., Graph Theory: An Introductory Course (1979), Springer: Springer Berlin · Zbl 0411.05032 |
| [2] | Burnside, W., Theory of Groups of Finite Order (1987), Cambridge · JFM 28.0118.03 |
| [3] | Cayley, A., On the theory of groups, Proc. London Math. Soc., 1, 9, 126-133 (1878) · JFM 10.0104.01 |
| [4] | Cayley, A., The theory of groups: graphical representations, Amer. J. Math., 1, 174-176 (1878) · JFM 10.0105.02 |
| [5] | Cayley, A., On the theory of groups, Amer. J. Math., 11, 139-157 (1889) · JFM 20.0140.01 |
| [6] | Choffrut, C.; Culik, K., On real-time cellular automata and trellis automata, Acta Inform., 21, 393-407 (1984) · Zbl 0534.68039 |
| [7] | Duke, R. A., The genus, regional number, and Betti number of graph, Canad. J. Math., 18, 817-822 (1979) · Zbl 0141.21302 |
| [8] | Dyer, C. R., One way bounded cellular automata, Inform. and Control, 44, 261-281 (1980) · Zbl 0442.68082 |
| [9] | Moser, W. O.J.; Coxeter, H. S.M., Generators And Relations For Discrete Groups (1965), Springer: Springer Berlin · Zbl 0133.28002 |
| [10] | Smit, A. R., Real-time language recognition by one-dimensional cellular automata, J. Comput. System Sci., 6, 233-253 (1972) · Zbl 0268.68044 |
| [11] | White, A. T., Graphs, Groups and Surfaces, (North-Holland Mathematics Studies (1973), North-Holland: North-Holland Amsterdam) · Zbl 0378.05028 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
