Skip to main content

Research Repository

Advanced Search

Computational complexity of threshold automata networks under different updating schemes

Goles, Eric; Montealegre, Pedro

Authors

Eric Goles

Pedro Montealegre



Abstract

© 2014 Elsevier B.V. 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.

Citation

Goles, E., & Montealegre, P. (2014). Computational complexity of threshold automata networks under different updating schemes. Theoretical Computer Science, 559, 3-19. https://doi.org/10.1016/j.tcs.2014.09.010

Journal Article Type Article
Acceptance Date Sep 11, 2014
Online Publication Date Sep 16, 2014
Publication Date Nov 20, 2014
Deposit Date Mar 5, 2020
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 559
Pages 3-19
DOI https://doi.org/10.1016/j.tcs.2014.09.010
Keywords Automata networks; Threshold functions; Computational complexity; Updating scheme; P-completeness; NC; NP-Hard
Public URL https://uwe-repository.worktribe.com/output/5608304
Additional Information This article is maintained by: Elsevier; Article Title: Computational complexity of threshold automata networks under different updating schemes; Journal Title: Theoretical Computer Science; CrossRef DOI link to publisher maintained version: https://doi.org/10.1016/j.tcs.2014.09.010; Content Type: article; Copyright: Copyright © 2014 Elsevier B.V. All rights reserved.