Folding Transducers

The class of polyregular functions is a class of string-to-string transducers. Among several other possibilities, this class can be characterised as the least class of functions that contains certain prime functions and is closed under certain combinators. For example, one of the combinators is map: if a function f: τ -> σ is polyregular, then the same is true for the function f*: τ* -> σ* that applies f to each list element. In this talk, I will discuss what happens if we want to add the fold combinator, as in functional programming languages. It turns out that with a more refined type system, inspired by linear logic, the fold combinator preserves polyregular functions.

Authors

• Mikołaj Bojańczyk

Keywords

No keywords are indexed for this paper.