Seminar series
Date
Thu, 03 Mar 2022
11:30
Location
C6
Speaker
Mikołaj Bojańczyk
Organisation
University of Warsaw/University of Oxford

MSO can be used not only to accept/reject words, but also to transform words into other words, e.g. the doubling function w $\mapsto$ ww. The traditional model for this is called MSO transductions; the idea is that each position of the output word is interpreted in some position of the input word, and MSO is used to define the order on output positions and their labels. I will explain that an extension, where output positions are interpreted using $k$-tuples of input positions, is (a) is also well behaved; and (b) this is surprising.

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.