A machine independent characterisation of the rational string-to-string functions

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

10 czerwca 2026 14:15

Pokój

p. 5440

Tytuł w języku polskim

A machine independent characterisation of the rational string-to-string functions

Seminarium

Seminarium „Teoria automatów”

---

This is a not-my-theorem talk. The subject is the rational string-to-string functions, which are those that can be computed by unambiguous automata with output. I will present a Myhill-Nerode style characterisation of these functions, which is due to Reutenauer and Schützenberger. The theorem is non-trivial, and one of the main difficulties is that there is no canonical device.

---