Polyregular functions

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

Dec. 19, 2018, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.  

---