Reachability problems for sequential dynamical systems with threshold functions

✍ Scribed by Chris Barrett; Harry B. Hunt III; Madhav V. Marathe; S.S. Ravi; Daniel J. Rosenkrantz; Richard E. Stearns

• Book ID: 104325487
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 220 KB
• Volume: 295
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00395-x

✦ Synopsis

A sequential dynamical system (SDS) over a domain D is a triple (G; F; ), where (i) G(V; E) is an undirected graph with n nodes with each node having a state value from D, (ii) F = {f1; f2; : : : ; fn} is a set of local transition functions with fi denoting the local transition function associated with node vi and (iii) is a permutation of (i.e., a total order on) the nodes in V . A single SDS transition is obtained by updating the states of the nodes in V by evaluating the function associated with each of them in the order given by .

We consider reachability problems for SDSs with restricted local transition functions. Our main intractability results show that the reachability problems for SDSs are PSPACE-complete when either of the following restrictions hold: (i) F consists of both simple-threshold-functions and simple-inverted-threshold functions, or (ii) F consists only of threshold-functions that use weights in an asymmetric manner. Moreover, the results hold even for SDSs whose underlying graphs have bounded node degree and bounded pathwidth. Our lower bound results also extend to reachability problems for Hopÿeld networks and communicating ÿnite state machines.

On the positive side, we show that when F consists only of threshold functions that use weights in a symmetric manner, reachability problems can be solved e ciently provided all the A preliminary version of some of the results in this paper were reported in [3].