A gentle introduction to bifix codes and dendric languages

Prelegent(ci)

Francesco Dolce

Afiliacja

Czech Technical University in Prague

Język referatu

angielski

Termin

26 marca 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

A gentle introduction to bifix codes and dendric languages

Seminarium

Seminarium „Teoria automatów”

---

A code is a set of words over an alphabet which can be uniquely decoded when concatenated. It is a bifix code if none of its elements is a prefix or a suffix of another one.

Dendric languages form a family of formal languages defined by a property on the possible extensions of its elements. They contain several well-known subfamilies: Sturmian, regular Interval Exchanges, etc.

In this talk we give a gentle introduction to these two notions and connect them by presenting several results with cool names (Maximal Bifix Decoding Theorem, Finite Index Property Theorem, Return Theorem, Freeness Theorem, Saturation Theorem).

In the process we show how to connect topics from various fields such as combinatorics on words, formal languages, codes, automata and free groups.

---