# Folding interpretations

arXiv: https://arxiv.org/abs/2301.05101 · HTML: https://mlsanity.com/paper/2301.05101/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jan 2023.

## Built on by (most cited first, 1 of 1)

- [The single-use restriction for register automata and transducers over infinite alphabets](https://mlsanity.com/paper/2406.18934/) (2024)

## Abstract (arXiv)

We study the polyregular string-to-string functions, which are certain functions of polynomial output size that can be described using automata and logic. We describe a system of combinators that generates exactly these functions. Unlike previous systems, the present system includes an iteration mechanism, namely fold. Although unrestricted fold can define all primitive recursive functions, we identify a type system (inspired by linear logic) that restricts fold so that it defines exactly the polyregular functions. We also present related systems, for quantifier-free functions as well as for linear regular functions on both strings and trees.