Relating the power of cellular arrays to their closure properties
From MaRDI portal
Publication:1104098
DOI10.1016/0304-3975(88)90040-0zbMATH Open0646.68071OpenAlexW1979559409MaRDI QIDQ1104098FDOQ1104098
Authors: 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
Recommendations
- Closure properties of cellular automata
- scientific article; zbMATH DE number 4028909
- On One-Way Cellular Arrays
- scientific article; zbMATH DE number 4026832
- On cellular-compactness and related properties
- Self-closeness numbers of finite cell complexes
- scientific article; zbMATH DE number 4106255
- scientific article; zbMATH DE number 177187
- Estimates of effective characteristics of random cell structures in terms of effective characteristics of periodic structures
- scientific article; zbMATH DE number 17391
concatenationcellular array languagecellular arrayslanguage recognition powerlinear-time cellular arraysreal-time cellular array
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- On One-Way Cellular Arrays
- Systolic trellis automatata †
- Real-time language recognition by one-dimensional cellular automata
- On real-time cellular automata and trellis automata
- Cellular automata complexity trade-offs
- Title not available (Why is that?)
- Deterministic one-way simulation of two-way real-time cellular automata and its related problems
- Tape bounds for time-bounded Turing machines
- On Some Open Problems in the Theory of Cellular Automata
Cited In (19)
- Languages not recognizable in real time by one-dimensional cellular automata
- On real time one-way cellular array
- Language not recognizable in real time by one-way cellular automata
- Closure properties of cellular automata
- Real time recognition with cellular automata : a meaningful example
- Constructible functions in cellular automata and their applications to hierarchy results
- Pushdown cellular automata
- Theory of cellular automata: a survey
- Signals in one-dimensional cellular automata
- On hardest languages for one-dimensional cellular automata
- On some open problems concerning the complexity of cellular arrays
- Two-dimensional cellular automata and deterministic on-line tessalation automata
- Some results on time-varying and relativised cellular automata*
- Language classes defined by time-bounded relativised cellular automata
- On hardest languages for one-dimensional cellular automata
- Non-deterministic cellular automata and languages
- Title not available (Why is that?)
- Low complexity classes of multidimensional cellular automata
- Nondeterministic, probabilistic and alternating computations on cellular array models
This page was built for publication: Relating the power of cellular arrays to their closure properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104098)
