Fast parallel language recognition by cellular automata

Oscar H. Ibarra, Michael A. Palis, Sam M. Kim

Research output: Contribution to journalArticlepeer-review


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 1 2(T(n) + 1) time. As a corollary, CA's can accept the linear, Dyck, and bracketed context-free languages in 1 2(n + 1) time, which is again optimal. We also study CA's with other modes of acceptance and derive results concerning speed-up, hierarchy, etcetera.

Original languageAmerican English
Pages (from-to)231-246
Number of pages16
JournalTheoretical Computer Science
Issue numberC
StatePublished - 1985
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


  • Cellular automaton
  • constant time
  • context-free language
  • log n time


Dive into the research topics of 'Fast parallel language recognition by cellular automata'. Together they form a unique fingerprint.

Cite this