On the complexity of generalized Q2R automaton

Eric Goles; Marco Montalva-Medel; Pedro Montealegre; Martín Ríos-Wilson

doi:10.1016/j.aam.2022.102355

On the complexity of generalized Q2R automaton

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

3 Citas (Scopus)

Resumen

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.

Idioma original	Inglés
Número de artículo	102355
Publicación	Advances in Applied Mathematics
Volumen	138
DOI	https://doi.org/10.1016/j.aam.2022.102355
Estado	Publicada - jul. 2022
Publicado de forma externa	Sí

Acceder al documento

10.1016/j.aam.2022.102355

Citar esto

@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 = "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.",

}

TY - JOUR

T1 - On the complexity of generalized Q2R automaton

AU - Goles, Eric

AU - Montalva-Medel, Marco

AU - Montealegre, Pedro

AU - Ríos-Wilson, Martín

PY - 2022/7

Y1 - 2022/7

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Limit cycles

KW - P-complete

KW - Q2R networks

UR - https://www.scopus.com/pages/publications/85128526310

U2 - 10.1016/j.aam.2022.102355

DO - 10.1016/j.aam.2022.102355

M3 - Article

AN - SCOPUS:85128526310

SN - 0196-8858

VL - 138

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

M1 - 102355

ER -

On the complexity of generalized Q2R automaton

Resumen

Acceder al documento

Huella

Citar esto