Relating the power of cellular arrays to their closure properties
From MaRDI portal
Publication:1104098
DOI10.1016/0304-3975(88)90040-0zbMath0646.68071OpenAlexW1979559409MaRDI QIDQ1104098
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
concatenationcellular array languagecellular arrayslanguage recognition powerlinear-time cellular arraysreal-time cellular array
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
