Transducers and straight line programs

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

20 listopada 2024 14:15

Pokój

p. 5440

Tytuł w języku polskim

Transducers and straight line programs

Seminarium

Seminarium „Teoria automatów”

---

In this talk, a straight line program (SLP) is a context-free grammar that generates a single string. This can be viewed as a compression scheme, with the compressed string being possibly exponentially smaller than the original string. In this talk, I will be interested in transducers with the following property: given an SLP that represents an input string, we want to compute in polynomial time an SLP that represents the output string. It turns out that not all polyregular functions have this property, but all linear ones do. I will also state a conjecture about which non-linear polyregular functions have this property, which is connected with a subclass of the polyregular functions, called the polyblind functions, that was introduced by Nguyen and Pradic.

Joint work with Markus Lohrey

---