On the complexity of generalized Q2R automaton

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish
Article number102355
JournalAdvances in Applied Mathematics
Volume138
DOIs
StatePublished - Jul 2022
Externally publishedYes

Keywords

  • Computational complexity
  • Limit cycles
  • P-complete
  • Q2R networks

Fingerprint

Dive into the research topics of 'On the complexity of generalized Q2R automaton'. Together they form a unique fingerprint.

Cite this