A graph-dynamical interpretation of Kiselman's semigroups

DOI10.1007/S10801-014-0569-7MaRDI QIDQ2354059zbMATH OpenOpenAlexFDO

Authors Elena Collina, Alessandro D'Andrea

Publication date 10 July 2015

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.3460

zbMATH Keywords

Hecke-Kiselman monoidssequential dynamical systemupdate systems

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Abstract: A Sequential Dynamical System (SDS) is a quadruple (Gamma, S_i,f_i,w) consisting of a (directed) graph Gamma=(V,E), each of whose vertices iin V is endowed with a finite set state S_i and an update function f_i: prod_{j, i o j} S_j o S_i --- 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 Gamma is a directed acyclic graph, the dynamics monoid of every update system supported on Gamma naturally arises as a quotient of the Hecke-Kiselman monoid associated with Gamma. In the special case where Gamma = Gamma_n is the complete oriented acyclic graph on n vertices, we exhibit an update system whose dynamics monoid coincides with Kiselman's semigroup K_n, 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.

Review text

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\).

Recommendations

• Sequential dynamical systems over words
• Combinatorics of sequential dynamical systems
• On acyclic orientations and sequential dynamical systems
• Discrete, sequential dynamical systems
• Elements of a theory of simulation. II: Sequential dynamical systems.

Cites work

• A semigroup of operators in convexity theory
• An introduction to sequential dynamical systems
• Elements of a theory of computer simulation. I
• Elements of a theory of simulation. II: Sequential dynamical systems.
• Elements of a theory of simulation. III: Equivalence of SDS.
• Hecke-Kiselman monoids of small cardinality.
• Monoid algebras of projection functors.
• On Kiselman quotients of 0-Hecke monoids.
• On Kiselman's semigroup.
• On the structure of semigroups

Cited in

(6)

• Enumerating periodic orbits in sequential dynamical systems over graphs
• Normal form in Hecke-Kiselman monoids associated with simple oriented graphs
• Identities of Hecke-Kiselman monoids
• The word problem for Hecke-Kiselman monoids of type \(A_n\) and \(\widetilde{A}_n\)
• Flexible toggles and symmetric invertible asynchronous elementary cellular automata
• A complete classification of endomorphisms of Kiselman's semigroup

This page was built for publication: A graph-dynamical interpretation of Kiselman's semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354059)