Synchronization and mortality in finite automata

13^th February 2019, 14:00
Andrew Ryzhikov
Université Paris-Est

Abstract

We study approximation algorithms for two closely related problems: the problems of finding a short synchronizing and a short mortal word for a given prefix code. Intuitively, a synchronizing word is a word guaranteeing a unique interpretation, and a mortal word is a word guaranteeing no interpretations for any sequence of codewords containing it. We concentrate on the case of finite prefix codes and consider both the cases where the code is defined by listing all its codewords and where the code is defined by an automaton recognizing the star of the code.

This is a joint work with Marek Szyku?a (University of Wroclaw).