On One-Way Cellular Arrays

DOI10.1137/0216072zbMath0646.68070OpenAlexW1982718233MaRDI QIDQ3790658

Oscar H. Ibarra, Tao Jiang

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216072

zbMATH Keywords

computational complexityreal-timelinear-timealternating Turing machineone- way cellular arrayone-way iterative arrayparallel language recognizer

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Cellular automata (computational aspects) (68Q80)

Related Items (21)

Closure properties of cellular automata ⋮ Relating the power of cellular arrays to their closure properties ⋮ Language classes defined by time-bounded relativised cellular automata ⋮ Low complexity classes of multidimensional cellular automata ⋮ Variations of the firing squad problem and applications ⋮ Optimal simulation of tree arrays by linear arrays ⋮ On iterative and cellular tree arrays ⋮ Descriptional complexity of bounded context-free languages ⋮ Alternation on cellular automata ⋮ Inductive definitions in logic versus programs of real-time cellular automata ⋮ On some open problems concerning the complexity of cellular arrays ⋮ Synthesis, structure and power of systolic computations ⋮ Nondeterministic, probabilistic and alternating computations on cellular array models ⋮ On real time one-way cellular array ⋮ Iterative arrays with self-verifying communication cell ⋮ Constructible functions in cellular automata and their applications to hierarchy results ⋮ Pushdown cellular automata ⋮ Simulation of one-way cellular automata by Boolean circuits ⋮ Complexity of One-Way Cellular Automata ⋮ Non-deterministic cellular automata and languages ⋮ Parallel recognition of rational languages in plane cellular automata

This page was built for publication: On One-Way Cellular Arrays