Computational complexity of threshold automata networks under different updating schemes

Eric Goles, Pedro Montealegre

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the AND-OR rule (vertices take the And or the Or logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs.

Original languageEnglish
Pages (from-to)3-19
Number of pages17
JournalTheoretical Computer Science
Volume559
Issue numberC
DOIs
StatePublished - 2014

Keywords

  • Automata networks
  • Computational complexity
  • NC
  • NP-Hard
  • P-completeness
  • Threshold functions
  • Updating scheme

Fingerprint

Dive into the research topics of 'Computational complexity of threshold automata networks under different updating schemes'. Together they form a unique fingerprint.

Cite this