Synchronizing codes, finite monoids of matrices and unambiguous automata
Time: 11:00 -- Location: Salle Philippe Flajolet du LIX
We introduce a new family of maps, namely tree-decorated maps where the tree is not necessarily spanning. To study this class of maps, we define a bijection which allows us to deduce combinatorial results, recovering as a corollary some results about spanning-tree decorated maps, and to understand local limits. Finally, we discuss the possible metric scaling limit of this map: the shocked map. We give certain properties and give the conjectured continuum construction. This is a work in progress with Avelio Sepúlveda.A set of finite words over a finite alphabet is called a (variable length) code if no word can be represented in two different ways as a concatenation of words from X. A synchronizing word for a code is a word such that every its occurence in a sequence of codewords allows to cut the decoding process in two independent parts before and after the occurence of this word. Synchronizing words allow to stop error propagation in decoding and decode a sequence of codewords from an arbitrary position. I will explain the interplay between synchronizing words in codes, unambiguous automata and finite monoids of zero-one matrices and tell about some old and new results about the bounds on shortest synchronizing words. This is a joint work in progress with Dominique Perrin.