Nie jesteś zalogowany |
On the growth rate of polyregular functions
- Prelegent(ci)
- Mikołaj Bojańczyk
- Afiliacja
- MIM UW
- Termin
- 12 kwietnia 2023 14:15
- Pokój
- p. 5050
- Seminarium
- Seminarium „Teoria automatów”
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.
