Relating the power of cellular arrays to their closure properties

DOI10.1016/0304-3975(88)90040-0zbMath0646.68071OpenAlexW1979559409MaRDI QIDQ1104098

Oscar H. Ibarra, Tao Jiang

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/0304-3975(88)90040-0

zbMATH Keywords

concatenationcellular array languagecellular arrayslanguage recognition powerlinear-time cellular arraysreal-time cellular array

Mathematics Subject Classification ID

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

Related Items (18)

Closure properties of cellular automata ⋮ Real time recognition with cellular automata : a meaningful example ⋮ Language not recognizable in real time by one-way cellular automata ⋮ Language classes defined by time-bounded relativised cellular automata ⋮ Low complexity classes of multidimensional cellular automata ⋮ Some results on time-varying and relativised cellular automata^* ⋮ Two-dimensional cellular automata and deterministic on-line tessalation automata ⋮ On some open problems concerning the complexity of cellular arrays ⋮ On hardest languages for one-dimensional cellular automata ⋮ Nondeterministic, probabilistic and alternating computations on cellular array models ⋮ On real time one-way cellular array ⋮ Languages not recognizable in real time by one-dimensional cellular automata ⋮ Theory of cellular automata: a survey ⋮ On hardest languages for one-dimensional cellular automata ⋮ Constructible functions in cellular automata and their applications to hierarchy results ⋮ Pushdown cellular automata ⋮ Signals in one-dimensional cellular automata ⋮ Non-deterministic cellular automata and languages

Cites Work

• Unnamed Item
• On real-time cellular automata and trellis automata
• Deterministic one-way simulation of two-way real-time cellular automata and its related problems
• Relationships between nondeterministic and deterministic tape complexities
• Tape bounds for time-bounded Turing machines
• Real-time language recognition by one-dimensional cellular automata
• Systolic trellis automatata †
• On One-Way Cellular Arrays
• On Some Open Problems in the Theory of Cellular Automata
• Cellular automata complexity trade-offs

This page was built for publication: Relating the power of cellular arrays to their closure properties