This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any TM on any input. We also consider the computational cost of such simulations.

Chandesris, J., Dennunzio, A., Formenti, E., Manzoni, L. (2011). Computational Aspects of Asynchronous Cellular Automata. In 15th International Conference on Developments in Language Theory, DLT 2011; Milan; Italy; 19-22 July 2011 (pp.466-468). Berlin : Springer-Verlag [10.1007/978-3-642-22321-1_41].

Computational Aspects of Asynchronous Cellular Automata

DENNUNZIO, ALBERTO;MANZONI, LUCA
2011

Abstract

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any TM on any input. We also consider the computational cost of such simulations.
paper
Asynchronous Cellular Automata, Computational Aspects
English
Developments in Language Theory - 15th International Conference, DLT 2011
2011
Mauri, G; Leporati, A
15th International Conference on Developments in Language Theory, DLT 2011; Milan; Italy; 19-22 July 2011
978-3-642-22321-1
2011
6795
466
468
none
Chandesris, J., Dennunzio, A., Formenti, E., Manzoni, L. (2011). Computational Aspects of Asynchronous Cellular Automata. In 15th International Conference on Developments in Language Theory, DLT 2011; Milan; Italy; 19-22 July 2011 (pp.466-468). Berlin : Springer-Verlag [10.1007/978-3-642-22321-1_41].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/43540
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
Social impact