First-order List Functions

We define a class of functions, called first-order list functions, which manipulate objects such as lists, lists of lists, pairs of lists, lists of pairs of lists, etc. The definition is in the style of regular expressions: first-order list functions are constructed by starting with some basic functions (e.g., projections, or head and tail operations on lists) and putting them together using four combinators (most importantly, composition of functions). We show that first-order list functions are exactly the same as first-order transductions, under a suitable encoding of the inputs. Finally, we observe that first-order list functions can be efficiently evaluated (linear time, also AC0), and their equivalence problem is decidable.

This is joint work with Laure Daviaud and Krishna S.

Presentation slides are in html format. The link is:
https://www.mimuw.edu.pl/~bojan/slides/combinators/