Fast parallel language recognition by cellular automata

DOI10.1016/0304-3975(85)90073-8zbMath0591.68054OpenAlexW2090079828MaRDI QIDQ1075053

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

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90073-8

zbMATH Keywords

context-free languageslinear cellular automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Related Items

A symbiosis between cellular automata and genetic algorithms ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ On time reduction and simulation in cellular spaces ⋮ A study on learning robustness using asynchronous 1D cellular automata rules ⋮ A characterization of constant-time cellular automata computation ⋮ Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars. ⋮ The complexity of systolic dissemination of information in interconnection networks ⋮ Languages not recognizable in real time by one-dimensional cellular automata ⋮ A Study on the Automatic Generation of Asynchronous Cellular Automata Rules by Means of Genetic Algorithms ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Complexity-theoretic aspects of expanding cellular automata ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Lower bounds and hardness magnification for sublinear-time shrinking cellular automata

Cites Work

• Unnamed Item
• Unnamed Item
• Characterizations and computational complexity of systolic trellis automata
• Parallel language recognition in constant time by cellular automata
• Real-time language recognition by one-dimensional cellular automata
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• One-way bounded cellular automata
• Computational Complexity of One-Tape Turing Machine Computations