Stability and looping in connectionist models with asymmetric weights

Recently, researchers in artificial intelligence have been actively investigating various connectionist models of computation. The model that is often studied is that of an asynchronous symmetric network, in which a global energy measure can be established and used to prove that the network totally stabilizes. In this paper, we discuss asymmetric networks that might admit infinite activated computations. Within this framework, we define an operational semantics under a synchronous activation rule and similarly under a fair asynchronous rule. Using this semantics, we analyze flow properties of a circle-network with respect to a specification that characterizes oscillation. We further explore the complexity of the decidable question of whether or not a given asymmetric network totally stabilizes. It is shown that this problem is NP-hard, and is in PSPACE.We thank the Xerox Corporation University Grants Program for providing equipment used in the preparation of this paper. This work was supported by the Air Force Systems Command, Rome Air Development Center, Griffiss Air Force Base, New York 13441-5700, and the Air Force Office of Scientific Research, Boiling AFB, DC 20332 under Contract No. F30602-85-C-0008. This contract supports the Northeast Artificial Intelligence Consortium (NAIC). A preliminary version of this paper was presented at the Ninth European Meeting on Cybernetics and Systems Research, Vienna, Austria, April, 1988