Linear sequential dynamical systems, incidence algebras, and Mobius functions

A sequential dynamical system (SDS) consists of a graph, a set of local functions and an update schedule. A linear sequential dynamical system is an SDS whose local functions are linear. In this paper, we derive an explicit closed formula for any linear SDS as a synchronous dynamical system. We also show constructively, that any synchronous linear system can be expressed as a linear SDS, i.e. it can be written as a product of linear local functions. Furthermore, we study the connection between linear SDS and the incidence algebras of partially ordered sets (posets). Specifically, we show that the Mobius function of any poset can be computed via an SDS, whose graph is induced by the Hasse diagram of the poset. Finally, we prove a cut theorem for the MObius functions of posets with respect to certain chain decompositions. (C) 2018 Elsevier Inc. All rights reserved.