Skip to Main content Skip to Navigation
Journal articles

Computational complexity of threshold automata networks under different updating schemes

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.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-01315323
Contributor : Pedro Montealegre <>
Submitted on : Friday, May 13, 2016 - 2:21:17 AM
Last modification on : Friday, January 8, 2021 - 11:22:05 AM

Links full text

Identifiers

Citation

Eric Goles Chacc, Pedro Montealegre. Computational complexity of threshold automata networks under different updating schemes. Theoretical Computer Science, Elsevier, 2014, 559, pp.3-19. ⟨10.1016/j.tcs.2014.09.010⟩. ⟨hal-01315323⟩

Share

Metrics

Record views

135