A categorical characterisation of linear regular functions

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

MIM UW

Termin

24 maja 2023 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

We consider linear regular string-to-string functions, i.e. functions that are recognized by copyless streaming string transducers, or any of their equivalent models, such as deterministic two-way automata. Although this class of functions is clearly important, in particular because of the many equivalent models, it has the disadvantage that each of the known models has a somewhat elaborate syntax. (A similar situation arises for Turing machines, which are important but have elaborate syntax.) We address this issue by providing another equivalent model, which uses very minimal syntax. In particular, features such as “single use” or “linear size increase” are not an explicit part of the syntax; but only provable consequence of it. The characterisation uses finiteness-preserving functors from the category of semigroups to itself, together with an output function that is a natural transformation. Joint work with Lê Thành Dũng Nguyễn (Tito)

---