clarke@csri.toronto.edu (Jim Clarke) (02/03/89)
AI SEMINAR - Thursday, February 16, 11 a.m. in SF 1105
(SF = Sandford Fleming Building, 10 King's College Road)
Armin Haken
University of Toronto
"Connectionist Networks that Need Exponential Time to Stabilize"
The symmetric-edge connectionist network model has the following desirable
property: For any state of the network, a sequence of state changes on in-
dividual "unhappy" nodes will eventually lead to a stable state with no
unhappy nodes. Furthermore, if the edge weights confine themselves to a
polynomial range, this process takes at most polynomial time.
In this talk, a construction is shown that demonstrates that with no res-
triction on the magnitude of the edge weight, the settling process can take
exponentially many steps no matter which order the unhappy nodes are
changed. The talk explains the idea of embedding a binary counter in a
network and gives the motivation of the various ideas that make the counter
work.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
clarke@csri.toronto.edu or clarke@csri.utoronto.ca
or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke