A guide to tax-free travelling between codes, automata and matrices

Prelegent(ci)

Andrew Ryzhikov

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

29 stycznia 2025 14:15

Pokój

p. 3250

Tytuł w języku polskim

A guide to tax-free travelling between codes, automata and matrices

Seminarium

Seminarium „Teoria automatów”

---

In this tutorial talk, I will describe a tight and fruitful relationship between variable-length codes (bases of free submonoids of a free monoid), unambiguous finite automata and semigroups of zero-one matrices. I will concentrate on basic notions that are natural for all three worlds, in particular on completeness and rank. The latter is related to a generalisation of the Černý conjecture, which I will explain along with some other intriguing open problems.

---