2013/11/14 by Elena Collina, Collina, Elena, Alessandro D’Andrea +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Dynamical Systems (math.DS) #FOS: Mathematics #Group Theory (math.GR) #Mathematical Dynamics and Fractals #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1311.3460
openalex publication_date 2013/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A Sequential Dynamical System (SDS) is a quadruple (Γ, Si,fi,w) consisting of a (directed) graph Γ=(V,E), each of whose vertices i∈ V is endowed with a finite set state Si and an update function fi: ∏j, i → j Sj → Si --- we call this structure an \em update system --- and 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 in this paper we are interested in the dynamics monoid, whose elements are all possible evolutions. When Γis a directed acyclic graph, the dynamics monoid of every update system supported on Γnaturally arises as a quotient of the Hecke-Kiselman monoid associated with Γ. In the special case where Γ= Γn is the complete oriented acyclic graph on n vertices, we exhibit an update system whose dynamics monoid coincides with Kiselman's semigroup Kn, thus showing that the defining Hecke-Kiselman relations are optimal in this situation. We then speculate on how these results may extend to the general acyclic case.