Fast cellular automata with restricted inter-cell communication: computational capacity
A d-dimensional cellular automaton with sequential input mode is a d-dimensional grid of interconnected interacting finite automata. The distinguished automaton at the origin, the communication cell, is connected to the outside world and fetches the input sequentially. Often in the literature thi...
| Autores principales: | , |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2006
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/24390 |
| Aporte de: |
| id |
I19-R120-10915-24390 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Ciencias Informáticas Unbounded-action devices (e.g., cellular automata, circuits, networks of machines) Arrays Formal Languages Parallel Architectures |
| spellingShingle |
Ciencias Informáticas Unbounded-action devices (e.g., cellular automata, circuits, networks of machines) Arrays Formal Languages Parallel Architectures Kutrib, Martin Malcher, Andreas Fast cellular automata with restricted inter-cell communication: computational capacity |
| topic_facet |
Ciencias Informáticas Unbounded-action devices (e.g., cellular automata, circuits, networks of machines) Arrays Formal Languages Parallel Architectures |
| description |
A d-dimensional cellular automaton with sequential input mode is a d-dimensional grid of interconnected interacting finite automata.
The distinguished automaton at the origin, the communication cell, is connected to the outside world and fetches the input sequentially.
Often in the literature this model is referred to as iterative array.
We investigate d-dimensional iterative arrays and one-dimensional cellular automata operating in real and linear time, whose inter-cell communication is restricted to some constant number of bits independent of the number of states. It is known that even one-dimensional one-bit iterative arrays accept rather complicated languages such as {a<sup>p</sup>│prim} or {a<sup>2</sup><sup>n</sup>│n∈N}[16]. We show that there is an infinite strict double dimension-bit hierarchy. The computational capacity of the one-dimensional devices in question is compared with the power of communication-restricted two-way cellular automata. It turns out that the relations are quite diferent from the relations in the unrestricted case. On passing, we obtain an infinite strict bit hierarchy for real-time two-way cellular automata and, moreover, a very dense time hierarchy for every k-bit cellular automata, i.e., just one more time step leads to a proper superfamily of accepted languages. |
| format |
Objeto de conferencia Objeto de conferencia |
| author |
Kutrib, Martin Malcher, Andreas |
| author_facet |
Kutrib, Martin Malcher, Andreas |
| author_sort |
Kutrib, Martin |
| title |
Fast cellular automata with restricted inter-cell communication: computational capacity |
| title_short |
Fast cellular automata with restricted inter-cell communication: computational capacity |
| title_full |
Fast cellular automata with restricted inter-cell communication: computational capacity |
| title_fullStr |
Fast cellular automata with restricted inter-cell communication: computational capacity |
| title_full_unstemmed |
Fast cellular automata with restricted inter-cell communication: computational capacity |
| title_sort |
fast cellular automata with restricted inter-cell communication: computational capacity |
| publishDate |
2006 |
| url |
http://sedici.unlp.edu.ar/handle/10915/24390 |
| work_keys_str_mv |
AT kutribmartin fastcellularautomatawithrestrictedintercellcommunicationcomputationalcapacity AT malcherandreas fastcellularautomatawithrestrictedintercellcommunicationcomputationalcapacity |
| bdutipo_str |
Repositorios |
| _version_ |
1764820466150670336 |