Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów

 

Pebble minimization for polyregular functions


Prelegent: Nathan Lhote

2020-02-05 14:15

We show that a polyregular word-to-word function is regular if and only  its output size is at most linear in its input size.

Moreover a polyregular function can be realized by: a transducer with two pebbles if and only if its output

has quadratic size in its input, a transducer with three pebbles if and only if its output has cubic size in its input, etc. 

Moreover the characterization is decidable and, given a polyregular function, one can compute a transducer realizing it

with the minimal number of pebbles. We apply the result to mso interpretations from words to words.

We show that mso interpretations of dimension $k$ exactly coincide with $k$-pebble transductions.