Folding interpretations

Speaker(s)

Mikołaj Bojańczyk

Affiliation

MIM UW

Date

Nov. 16, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

---