A sequential dynamical system is a quadruple $$(\varGamma , S_i,f_i,w)$$(Γ,Si,fi,w) consisting of a (directed) graph $$\varGamma =(V,E)$$Γ=(V,E), each of whose vertices $$i\in V$$i∈V is endowed with a finite set state $$S_i$$Si and an update function $$f_i: \prod _{j, i \rightarrow j} S_j \rightarrow S_i$$fi:∏j,i→jSj→Si—we call this structure an update system—and a word $$w$$w in the free monoid over $$V$$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 $$\varGamma $$Γ is a directed acyclic graph, the dynamics monoid of every update system supported on $$\varGamma $$Γ naturally arises as a quotient of the Hecke–Kiselman monoid associated with $$\varGamma $$Γ. In the special case where $$\varGamma = \varGamma _n$$Γ=Γn is the complete oriented acyclic graph on $$n$$n vertices, we exhibit an update system whose dynamics monoid coincides with Kiselman’s semigroup $${K}_n$$Kn, thus showing that the defining Hecke–Kiselman relations are optimal in this situation. We then speculate on how these results may be extended to the general acyclic case.
Collina E., D'Andrea A. (2015). A graph-dynamical interpretation of Kiselman’s semigroups. JOURNAL OF ALGEBRAIC COMBINATORICS, 41(4), 1115-1132 [10.1007/s10801-014-0569-7].
A graph-dynamical interpretation of Kiselman’s semigroups
D'Andrea A.
2015
Abstract
A sequential dynamical system is a quadruple $$(\varGamma , S_i,f_i,w)$$(Γ,Si,fi,w) consisting of a (directed) graph $$\varGamma =(V,E)$$Γ=(V,E), each of whose vertices $$i\in V$$i∈V is endowed with a finite set state $$S_i$$Si and an update function $$f_i: \prod _{j, i \rightarrow j} S_j \rightarrow S_i$$fi:∏j,i→jSj→Si—we call this structure an update system—and a word $$w$$w in the free monoid over $$V$$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 $$\varGamma $$Γ is a directed acyclic graph, the dynamics monoid of every update system supported on $$\varGamma $$Γ naturally arises as a quotient of the Hecke–Kiselman monoid associated with $$\varGamma $$Γ. In the special case where $$\varGamma = \varGamma _n$$Γ=Γn is the complete oriented acyclic graph on $$n$$n vertices, we exhibit an update system whose dynamics monoid coincides with Kiselman’s semigroup $${K}_n$$Kn, thus showing that the defining Hecke–Kiselman relations are optimal in this situation. We then speculate on how these results may be extended to the general acyclic case.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.