Transductions Computed by One-Dimensional Cellular Automata
Cellular automata are investigated towards their ability to compute transductions, that is, to transform inputs into outputs. The families of transductions computed are classified with regard to the time allowed to process the input and to compute the output. Since there is a particular interest in...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2012-08-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1208.2768v1 |
| _version_ | 1828405929671917568 |
|---|---|
| author | Martin Kutrib Andreas Malcher |
| author_facet | Martin Kutrib Andreas Malcher |
| author_sort | Martin Kutrib |
| collection | DOAJ |
| description | Cellular automata are investigated towards their ability to compute transductions, that is, to transform inputs into outputs. The families of transductions computed are classified with regard to the time allowed to process the input and to compute the output. Since there is a particular interest in fast transductions, we mainly focus on the time complexities real time and linear time. We first investigate the computational capabilities of cellular automaton transducers by comparing them to iterative array transducers, that is, we compare parallel input/output mode to sequential input/output mode of massively parallel machines. By direct simulations, it turns out that the parallel mode is not weaker than the sequential one. Moreover, with regard to certain time complexities cellular automaton transducers are even more powerful than iterative arrays. In the second part of the paper, the model in question is compared with the sequential devices single-valued finite state transducers and deterministic pushdown transducers. It turns out that both models can be simulated by cellular automaton transducers faster than by iterative array transducers. |
| first_indexed | 2024-12-10T11:03:37Z |
| format | Article |
| id | doaj.art-60c25c0fb21c45439fee474316645a06 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-10T11:03:37Z |
| publishDate | 2012-08-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-60c25c0fb21c45439fee474316645a062022-12-22T01:51:37ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802012-08-0190Proc. AUTOMATA&JAC 201219420710.4204/EPTCS.90.16Transductions Computed by One-Dimensional Cellular AutomataMartin KutribAndreas MalcherCellular automata are investigated towards their ability to compute transductions, that is, to transform inputs into outputs. The families of transductions computed are classified with regard to the time allowed to process the input and to compute the output. Since there is a particular interest in fast transductions, we mainly focus on the time complexities real time and linear time. We first investigate the computational capabilities of cellular automaton transducers by comparing them to iterative array transducers, that is, we compare parallel input/output mode to sequential input/output mode of massively parallel machines. By direct simulations, it turns out that the parallel mode is not weaker than the sequential one. Moreover, with regard to certain time complexities cellular automaton transducers are even more powerful than iterative arrays. In the second part of the paper, the model in question is compared with the sequential devices single-valued finite state transducers and deterministic pushdown transducers. It turns out that both models can be simulated by cellular automaton transducers faster than by iterative array transducers.http://arxiv.org/pdf/1208.2768v1 |
| spellingShingle | Martin Kutrib Andreas Malcher Transductions Computed by One-Dimensional Cellular Automata Electronic Proceedings in Theoretical Computer Science |
| title | Transductions Computed by One-Dimensional Cellular Automata |
| title_full | Transductions Computed by One-Dimensional Cellular Automata |
| title_fullStr | Transductions Computed by One-Dimensional Cellular Automata |
| title_full_unstemmed | Transductions Computed by One-Dimensional Cellular Automata |
| title_short | Transductions Computed by One-Dimensional Cellular Automata |
| title_sort | transductions computed by one dimensional cellular automata |
| url | http://arxiv.org/pdf/1208.2768v1 |
| work_keys_str_mv | AT martinkutrib transductionscomputedbyonedimensionalcellularautomata AT andreasmalcher transductionscomputedbyonedimensionalcellularautomata |