First-order list functions

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

4 października 2017 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with Laure Daviaud and Krishna S

Seminarium

Seminarium „Teoria automatów”

---

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.

---