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

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

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	102355
Journal	Advances in Applied Mathematics
Volume	138
DOIs	https://doi.org/10.1016/j.aam.2022.102355
State	Published - Jul 2022
Externally published	Yes

Keywords

Computational complexity
Limit cycles
P-complete
Q2R networks

Access to Document

10.1016/j.aam.2022.102355

Cite this

@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 - http://www.scopus.com/inward/record.url?scp=85128526310&partnerID=8YFLogxK

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this