| Records |
| Author |
Goles, E.; Montealegre, P. |
| Title |
Computational complexity of threshold automata networks under different updating schemes |
Type |
|
| Year |
2014 |
Publication |
Theoretical Computer Science |
Abbreviated Journal |
Theor. Comput. Sci. |
| Volume |
559 |
Issue |
|
Pages |
3-19 |
| Keywords |
Automata networks; Threshold functions; Computational complexity; Updating scheme; P-completeness; NC; NP-Hard |
| 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. (C) 2014 Elsevier B.V. All rights reserved. |
| Address |
[Goles, Eric] Univ Adolfo Ibanez, Fac Ciencias & Tecnol, Santiago, Chile, Email: eric.chacc@uai.cl; |
| Corporate Author |
|
Thesis |
|
| Publisher |
Elsevier Science Bv |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0304-3975 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000347025300002 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
434 |
| Permanent link to this record |
| |
|
| |
| Author |
Goles, E.; Ruz, G.A. |
| Title |
Dynamics of neural networks over undirected graphs |
Type |
|
| Year |
2015 |
Publication |
Neural Networks |
Abbreviated Journal |
Neural Netw. |
| Volume |
63 |
Issue |
|
Pages |
156-169 |
| Keywords |
Neural networks; Undirected graphs; Discrete updating schemes; Attractors; Fixed points; Cycles |
| Abstract |
In this paper we study the dynamical behavior of neural networks such that their interconnections are the incidence matrix of an undirected finite graph G = (V, E) (i.e., the weights belong to {0, 1}). The network may be updated synchronously (every node is updated at the same time), sequentially (nodes are updated one by one in a prescribed order) or in a block-sequential way (a mixture of the previous schemes). We characterize completely the attractors (fixed points or cycles). More precisely, we establish the convergence to fixed points related to a parameter alpha(G), taking into account the number of loops, edges, vertices as well as the minimum number of edges to remove from E in order to obtain a maximum bipartite graph. Roughly, alpha(G') < 0 for any G' subgraph of G implies the convergence to fixed points. Otherwise, cycles appear. Actually, for very simple networks (majority functions updated in a block-sequential scheme such that each block is of minimum cardinality two) we exhibit cycles with nonpolynomial periods. (C) 2014 Elsevier Ltd. All rights reserved. |
| Address |
[Goles, Eric; Ruz, Gonzalo A.] Univ Adolfo Ibanez, Fac Ingn & Ciencias, Santiago, Chile, Email: eric.chacc@uai.cl; |
| Corporate Author |
|
Thesis |
|
| Publisher |
Pergamon-Elsevier Science Ltd |
Place of Publication |
|
Editor |
|
| Language |
English |
Summary Language |
|
Original Title |
|
| Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
| Series Volume |
|
Series Issue |
|
Edition |
|
| ISSN |
0893-6080 |
ISBN |
|
Medium |
|
| Area |
|
Expedition |
|
Conference |
|
| Notes |
WOS:000349730800015 |
Approved |
|
| Call Number |
UAI @ eduardo.moreno @ |
Serial |
460 |
| Permanent link to this record |
