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

 

Folding interpretations


Prelegent: Mikołaj Bojańczyk

2022-11-16 14:15

In this talk, I will discuss a characterisation of the polyregular functions which uses folding. The idea is to use the combinator approach, i.e. start with certain atomic functions (such as list concatenation) and apply certain combinators (such as function composition). However, we want one of the combinators to be folding, i.e. a combinator that inputs a transition function δ : Q x Σ -> Q from an automaton and returns the iterated transition function δ*: Q x Σ* -> Q. Folding, when Q is not necessarily finite, is a powerful combinator, and it takes some effort to impose restrictions which ensure that folding does not create a system that is Turing complete. This effort will be presented during the talk.