The synthesis of a linear Boolean net is still an open problem in the study of neural nets. The aim of this paper is to introduce a class for which the solution is possible in polynomial computational time. In this class, by considering a neural net of n elements, once the evolution of n independent states is fixed a priori, we compute the algorithms to construct the synaptic matrix and the evolution of the remaining 2n − n states. These algorithms work in polynomial computational time; the class contains 2n2 matrices. The main result is the proof that for the class under examination the complete evolution of the net is fixed by an n × n permutation matrix P0 which connects the n independent states with their next successors. This reduces the time needed to study an arbitrary linear Boolean net from exponential to polynomial in the number of neurons. All information concerning the existence and identification of cycles, attractors, and transient states is contained in and easily retrievable from P0.

Classes of efficiently computable linear Neural Nets

TAGLIAFERRI, Roberto
1990-01-01

Abstract

The synthesis of a linear Boolean net is still an open problem in the study of neural nets. The aim of this paper is to introduce a class for which the solution is possible in polynomial computational time. In this class, by considering a neural net of n elements, once the evolution of n independent states is fixed a priori, we compute the algorithms to construct the synaptic matrix and the evolution of the remaining 2n − n states. These algorithms work in polynomial computational time; the class contains 2n2 matrices. The main result is the proof that for the class under examination the complete evolution of the net is fixed by an n × n permutation matrix P0 which connects the n independent states with their next successors. This reduces the time needed to study an arbitrary linear Boolean net from exponential to polynomial in the number of neurons. All information concerning the existence and identification of cycles, attractors, and transient states is contained in and easily retrievable from P0.
1990
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/3384078
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact