joint work with Laure Daviaud and Krishna S

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

Oct. 4, 2017, 2:15 p.m.

Room

room 5870

Title in Polish

First-order list functions

Seminar

Seminar Automata Theory

---

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.

---