You are not logged in |
On the growth rate of polyregular functions
- Speaker(s)
- Mikołaj Bojańczyk
- Affiliation
- MIM UW
- Date
- April 12, 2023, 2:15 p.m.
- Room
- room 5050
- Seminar
- Seminar Automata Theory
Polyregular functions are string-to-string functions that have polynomial size outputs. I will show that a polyregular function has growth rate O(n^k) if and only if it can be defined by an mso transduction of dimension k. On the other hand, the former two conditions are not equivalent to k-pebble automata; in fact there are polyregular functions of quadratic growth that require arbitrary numbers of pebbles to be computed.
