Polyregular functions

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

19 grudnia 2018 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

I will describe a class of string-to-string transducers, which goes beyond rational or regular functions, but still shares many of their good properties (e.g. the inverse image of a regular language is regular). Unlike many string-to-string transducer models (including sequential, rational and regular transducers), which have linear size increase, the the new class (called polyregular functions) has polynomial size increase.

The main selling point of the polyregular functions is that they admit numerous equivalent descriptions: (a) automata with pebbles; (b) a fragment of lambda calculus; (c) a fragment of for-programs; and (d) compositions of certain atomic functions, such as reverse or a form of string squaring. Also, most likely (this is still ongoing work): (e) mso string-to-string interpretations.  

---