Eric Goles
Computational complexity of threshold automata networks under different updating schemes
Goles, Eric; Montealegre, Pedro
Authors
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. |
Downloadable Citations
About UWE Bristol Research Repository
Administrator e-mail: repository@uwe.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search