Regular and First-Order List Functions

DOI10.1145/3209108.3209163zbMATH Open1497.68137arXiv1803.06168OpenAlexW2963346678MaRDI QIDQ5145284FDOQ5145284

Authors: Mikołaj Bojańczyk, Laure Daviaud, Shankara Narayanan Krishna 

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1803.06168

Recommendations

• scientific article; zbMATH DE number 3906787
• First-Class Functions
• scientific article; zbMATH DE number 1256736
• Publication:3472340
• First-order logic and first-order functions
• Publication:2757839
• The characterization of orders for regular functions
• scientific article; zbMATH DE number 3884443
• A generalization of functions of the first class

Mathematics Subject Classification ID

Data structures (68P05) Logic in computer science (03B70)

Cited In (4)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Transducers of polynomial growth

This page was built for publication: Regular and First-Order List Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145284)