A sequential dynamical system is a quadruple consisting of a (directed) graph , each of whose vertices is endowed with a finite set state and an update function -we call this structure an update system-and a word in the free monoid over , 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 is the complete oriented acyclic graph on vertices, we exhibit an update system whose dynamics monoid coincides with Kiselman's semigroup , 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.

A graph-dynamical interpretation of Kiselman’s semigroups / Collina, Elena; D'Andrea, Alessandro. - In: JOURNAL OF ALGEBRAIC COMBINATORICS. - ISSN 0925-9899. - STAMPA. - 41:4(2015), pp. 1115-1132. [10.1007/s10801-014-0569-7]

A graph-dynamical interpretation of Kiselman’s semigroups

COLLINA, elena;D'ANDREA, Alessandro
2015

Abstract

A sequential dynamical system is a quadruple consisting of a (directed) graph , each of whose vertices is endowed with a finite set state and an update function -we call this structure an update system-and a word in the free monoid over , 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 is the complete oriented acyclic graph on vertices, we exhibit an update system whose dynamics monoid coincides with Kiselman's semigroup , 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.
2015
Hecke–Kiselman monoids; sequential dynamical system; update systems; discrete mathematics and combinatorics; algebra and number theory
01 Pubblicazione su rivista::01a Articolo in rivista
A graph-dynamical interpretation of Kiselman’s semigroups / Collina, Elena; D'Andrea, Alessandro. - In: JOURNAL OF ALGEBRAIC COMBINATORICS. - ISSN 0925-9899. - STAMPA. - 41:4(2015), pp. 1115-1132. [10.1007/s10801-014-0569-7]
File allegati a questo prodotto
File Dimensione Formato  
Collina_Graph-dynamical_2015.pdf

accesso aperto

Note: Articolo principale
Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 252.39 kB
Formato Adobe PDF
252.39 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/817372
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact