@article{27fa2adc96eb40078b7548ffa3e766e2,
title = "On the complexity of generalized Q2R automaton",
abstract = "We study the dynamic and complexity of the generalized Q2R automaton. We show the existence of non-polynomial cycles as well as its capability to simulate with the synchronous update the classical version of the automaton updated under a block sequential update scheme. Furthermore, we show that the decision problem consisting in determine if a given node in the network changes its state is P-Hard.",
keywords = "Computational complexity, Limit cycles, P-complete, Q2R networks",
author = "Eric Goles and Marco Montalva-Medel and Pedro Montealegre and Mart{\'i}n R{\'i}os-Wilson",
note = "Funding Information: ANID via FONDECYT 1200006 + STIC- AmSud CoDANet project 19-STIC-03.ANID via PAI + Convocatoria Nacional Subvenci{\'o}n a la Incorporaci{\'o}n en la Academia A{\~n}o 2017 + PAI77170068, FONDECYT 11190482, FONDECYT 1200006, STIC- AmSud CoDANet project 19-STIC-03.ANID via PFCHA/DOCTORADO NACIONAL/2018 – 21180910 + PIA AFB 170001, French ANR project FANs ANR-18-CE40-0002 and ECOS project C19E02. Publisher Copyright: {\textcopyright} 2022 Elsevier Inc.",
year = "2022",
month = jul,
doi = "10.1016/j.aam.2022.102355",
language = "English",
volume = "138",
journal = "Advances in Applied Mathematics",
issn = "0196-8858",
publisher = "Academic Press Inc.",
}