Computational complexity of threshold automata networks under different updating schemes

Goles, Eric; Montealegre, Pedro

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.