Deterministic one-way simulation of two-way real-time cellular automata and its related problems

DOI10.1016/0020-0190(82)90028-XzbMath0488.68041OpenAlexW1970863182MaRDI QIDQ1166274

Hiroshi Umeo, Kenichi Morita, Kazuhiro Sugata

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90028-x

zbMATH Keywords

parallel computationparallel processingcircular cellular automatadeterministic one-way cellular automatondeterministic two-way real- time cellular automaton

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Theory of operating systems (68N25)

Related Items

Two-dimensional iterative arrays: Characterizations and applications ⋮ Relating the power of cellular arrays to their closure properties ⋮ On iterative and cellular tree arrays ⋮ Unnamed Item ⋮ Self-verifying Cellular Automata ⋮ Simulation of one-dimensional cellular automata by uniquely parallel parsable grammars. ⋮ On some open problems concerning the complexity of cellular arrays ⋮ Estimates of the operating time of stable iterative, language-modeling, and recognition systems ⋮ Languages not recognizable in real time by one-dimensional cellular automata ⋮ Constructible functions in cellular automata and their applications to hierarchy results ⋮ Complexity of One-Way Cellular Automata ⋮ Real-Time Reversible One-Way Cellular Automata ⋮ Non-deterministic cellular automata and languages ⋮ Computation theoretic aspects of cellular automata ⋮ Systolic trellis automatata † ⋮ Systolic trellis automatat† ⋮ Topological transformations as a tool in the design of systolic networks

Cites Work

• Real-time language recognition by one-dimensional cellular automata
• One-way bounded cellular automata