Stability and looping in connectionist models with asymmetric weights (Q1115639)

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. 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.