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

Speaker(s)

Andrew Ryzhikov

Affiliation

University of Warsaw

Language of the talk

English

Date

Jan. 29, 2025, 2:15 p.m.

Room

room 3250

Title in Polish

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

Seminar

Seminar Automata Theory

---

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.

---