Matrix method for linear sequential dynamical systems on digraphs

In this paper, we introduce the concept of sequential dynamical systems (SDS) on digraphs. We focus on the discussion of linear sequential dynamical systems (LSDS). Matrix method is given in their analysis. Two special LSDS, OR-SDS and PAR-SDS, are particularly analyzed. Some structural properties on the image spaces of [ORD, pi] and [PAR(D); pi] are obtained. The asymptotic behavior of [ORD, pi] is described in terms of the properties of the digraph D with respect to the ordering pi. Our results show that LSDS on digraphs have much more interesting properties than those on undirected graphs. (C) 2003 Elsevier Inc. All rights reserved.