Cellular Automata (CA) are a well-established bio-inspired model of computation that has been successfully applied in several domains. In the recent years the importance of modelling real systems more accurately has sparkled a new interest in the study of asynchronous CA (ACA). When using an ACA for modelling real systems, it is important to determine the fidelity of the model, in particular with regards to the existence (or absence) of certain dynamical behaviors. This paper is concerned with two big classes of problems: reachability and preimage existence. For each class, both an existential and a universal version are considered. The following results are proved. Reachability is PSPACE-complete, its resource bounded version is NP-complete (existential form) or coNP-complete (universal form). The preimage problem is dimension sensitive in the sense that it is NL-complete (both existential and universal form) for one-dimensional ACA while it is NP-complete (existential version) or Π2P-complete (universal version) for higher dimension.

Dennunzio, A., Formenti, E., Manzoni, L., Mauri, G., Porreca, A. (2017). Computational complexity of finite asynchronous cellular automata. THEORETICAL COMPUTER SCIENCE, 664, 131-143 [10.1016/j.tcs.2015.12.003].

Computational complexity of finite asynchronous cellular automata

DENNUNZIO, ALBERTO
Primo
;
MANZONI, LUCA;MAURI, GIANCARLO
;
PORRECA, ANTONIO ENRICO
Ultimo
2017

Abstract

Cellular Automata (CA) are a well-established bio-inspired model of computation that has been successfully applied in several domains. In the recent years the importance of modelling real systems more accurately has sparkled a new interest in the study of asynchronous CA (ACA). When using an ACA for modelling real systems, it is important to determine the fidelity of the model, in particular with regards to the existence (or absence) of certain dynamical behaviors. This paper is concerned with two big classes of problems: reachability and preimage existence. For each class, both an existential and a universal version are considered. The following results are proved. Reachability is PSPACE-complete, its resource bounded version is NP-complete (existential form) or coNP-complete (universal form). The preimage problem is dimension sensitive in the sense that it is NL-complete (both existential and universal form) for one-dimensional ACA while it is NP-complete (existential version) or Π2P-complete (universal version) for higher dimension.
Articolo in rivista - Articolo scientifico
Asynchronous cellular automata; Computational complexity; Natural computing
English
11-dic-2015
2017
664
131
143
reserved
Dennunzio, A., Formenti, E., Manzoni, L., Mauri, G., Porreca, A. (2017). Computational complexity of finite asynchronous cellular automata. THEORETICAL COMPUTER SCIENCE, 664, 131-143 [10.1016/j.tcs.2015.12.003].
File in questo prodotto:
File Dimensione Formato  
paper.pdf

Solo gestori archivio

Descrizione: Preprint
Tipologia di allegato: Submitted Version (Pre-print)
Dimensione 270.51 kB
Formato Adobe PDF
270.51 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
pubblicazione5.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 473.71 kB
Formato Adobe PDF
473.71 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/107082
Citazioni
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 15
Social impact