A graph-dynamical interpretation of Kiselman's semigroups (Q2354059)

A sequential dynamical system (SDS) is a quadruple \((\Gamma, S_i,f_i,w)\) consisting of a directed graph \(\Gamma=(V,E)\); an update system: each of whose vertices \(i \in V\) is endowed with a finite set state \(S_i\) and an update function \(f_i: \prod_{j, i \to j} S_j \to S_i\); a word \(w\) in the free monoid over \(V,\) specifying the order in which update functions are to be performed. Each word induces an evolution of the system and the authors are interested in the dynamics monoid, whose elements are all possible evolutions. The authors prove that if \(\Gamma\) is a directed acyclic graph, then the dynamics monoid of every update system supported on \(\Gamma\) naturally arises as a quotient of the \(\operatorname{HK}_\Gamma\), the Hecke-Kiselman monoid associated with \(\Gamma.\) Moreover, in the special case where \(\Gamma = \Gamma_n\) is the complete oriented acyclic graph on \(n\) vertices, they show an update system whose dynamics monoid coincides with Kiselman's semigroup \(K_n\).