FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Regular and First Order List Functions

Authors: Mikolaj Bojanczyk, Laure Daviaud and Krishna Shankara Narayanan

Paper Information

Title:Regular and First Order List Functions
Authors:Mikolaj Bojanczyk, Laure Daviaud and Krishna Shankara Narayanan
Proceedings:LICS PDF files
Editors: Anuj Dawar and Erich Grädel
Keywords:First order transduction, MSO transduction, Streaming string transducers, First-order list function
Abstract:

ABSTRACT. We define two classes of functions, called regular (respectively, 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: the functions are constructed by starting with some basic functions (e.g. projections from pairs, or head and tail operations on lists) and putting them together using four combinators (most importantly, composition of functions). Our main results are that first-order list functions are exactly the same as first-order transductions, under a suitable encoding of the inputs; and the regular list functions are exactly the same as MSO-transductions.

Pages:10
Talk:Jul 09 12:20 (Session 47D)
Paper: