Folding interpretations

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

MIM UW

Termin

16 listopada 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.

---