Abstract | ||
---|---|---|
This paper studies the capabilities of one dimensional, neighborhood of radius one cellular automata to construct speed one signals. We define the notions of constructibility, consistent constructibility and preserving complexity consistent constructibility. Our main results are the following. • There exists a one dimensional neighborhood of radius one cellular automaton with four states which preserving complexity consistently constructs (E*), the set of all speed one signals with a finite number of changes of direction. • The class of speed one signal preserving complexity consistently constructed by any one dimensional neighborhood of radius one cellular automaton with three states is a proper subclass of (E*). |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S0012-365X(02)00499-5 | Discrete Mathematics |
Keywords | Field | DocType |
main result,complexity consistent constructibility,finite number,cellular automaton,cellular automata,consistent constructibility,dimensional neighborhood,paper study,signal constructibility,proper subclass | Cellular automaton,Discrete mathematics,Continuous automaton,Combinatorics,Finite set,Existential quantification,Mobile automaton,Reversible cellular automaton,Block cellular automaton,Stochastic cellular automaton,Mathematics | Journal |
Volume | Issue | ISSN |
262 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martín Matamala | 1 | 158 | 21.63 |