A categorical characterisation of linear regular functions

Speaker(s)

Mikołaj Bojańczyk

Affiliation

MIM UW

Date

May 24, 2023, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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)

---