You are not logged in | Log in

PL /
EN

Speaker(s): Mikołaj Bojańczyk
Affiliation: University of Warsaw
Language of the talk: English
Date: June 10, 2026, 2:15 p.m.
Room: room 5440
Title in Polish: A machine independent characterisation of the rational string-to-string functions
Seminar: Seminar Automata Theory

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.