Transducers and straight line programs

Speaker(s)

Mikołaj Bojańczyk

Affiliation

University of Warsaw

Language of the talk

English

Date

Nov. 20, 2024, 2:15 p.m.

Room

room 5440

Title in Polish

Transducers and straight line programs

Seminar

Seminar Automata Theory

---

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

---