zbMATH — the first resource for mathematics

Fast parallel language recognition by cellular automata. (English) Zbl 0591.68054
Summary: We look at linear cellular automata (CA’s) which accept an input if and only if at some time during the computation all the processors in the array are in accepting states. We prove that there are noncontext-free languages that are accepted by CA’s in O(log n) time. Moreover, this is the best possible since o(log n) time CA’s can accept only regular sets. We show that one-way CA’s operating in T(n) time can be simulated by CA’s in \((T(n)+1)\) time. As a corollary, CA’s can accept the linear, Dyck, and bracketed context-free languages in \((n+1)\) time, which is again optimal. We also study CA’s with other modes of acceptance and derive results concerning speed-up, hierarchy, etc.

68Q80 Cellular automata (computational aspects)
68Q45 Formal languages and automata
Full Text: DOI
[1] Codd, E., Cellular automata, (1968), Academic Press New York · Zbl 0213.18301
[2] Dyer, C., One-way bounded cellular automata, Inform. and control, 44, 261-281, (1980) · Zbl 0442.68082
[3] Hartmanis, J., Computational complexity of one-tape Turing machine computations, J. ACM, 15, 325-339, (1968) · Zbl 0162.31703
[4] Ibarra, O.H.; Kim, S.M., Characterizations and computational complexity of systolic Trellis automata, Theoret. comput. sci., 29, 123-153, (1984) · Zbl 0536.68048
[5] Ibarra, O.H.; Kim, S.M.; Moran, S., Sequential machine characterizations of Trellis and cellular automata and applications, SIAM J. comput., 14, 426-447, (1985) · Zbl 0574.68044
[6] O. H. Ibarra, S. M. Kim and M. A. Palis, Designing systolic algorithms using sequential machines, IEEE Trans. Comput., to appear.
[7] Rosenfeld, A., Picture languages, (1979), Academic Press New York · Zbl 0471.68074
[8] Smith, A., Real-time language recognition by one-dimensional cellular automata, Comput. system sci., 6, 233-253, (1972) · Zbl 0268.68044
[9] Sommerhelder, R.; van Westrhenen, S., Parallel language recognition in constant time by cellular automata, Acta inform., 19, 397-407, (1983) · Zbl 0492.68061
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.