Languages not recognizable in real time by one-dimensional cellular automata

DOI10.1016/J.JCSS.2007.06.023zbMath1152.68034OpenAlexW2011044793WikidataQ126252818 ScholiaQ126252818MaRDI QIDQ955338

Katsuhiko Nakamura

Publication date: 19 November 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.06.023

zbMATH Keywords

OCACAclosure under concatenationparallel language recognitionreal-time recognition

Mathematics Subject Classification ID

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

Cites Work

• On real time one-way cellular array
• On real-time cellular automata and trellis automata
• Closure properties of cellular automata
• Fast parallel language recognition by cellular automata
• Relating the power of cellular arrays to their closure properties
• Deterministic one-way simulation of two-way real-time cellular automata and its related problems
• Signals in one-dimensional cellular automata
• Language not recognizable in real time by one-way cellular automata
• Real-time language recognition by one-dimensional cellular automata
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Generation of Primes by a One-Dimensional Real-Time Iterative Array
• Cellular automata complexity trade-offs

This page was built for publication: Languages not recognizable in real time by one-dimensional cellular automata