2023/01/12 by Mikołaj Bojańczyk, Bojańczyk, Mikołaj
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Natural Language Processing Techniques #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2301.05101
openalex publication_date 2023/01/12 · openalex created_date 2023/01/14 · openalex updated_date 2026/07/28
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.