Laboratoire d'informatique de l'École polytechnique

Talk by Andrew Ryzhikov: «Synchronizing codes, finite monoids of matrices and unambiguous automata»

Speaker: Andrew Ryzhikov
Location: Room Flajolet
Date: Wed, 13 Mar 2019, 11:00-12:00

The first talk of the next Plateau Saclay Combinatorics Seminar will be given by Andrew Ryzhikov.

Abstract: 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.