Regular and First-Order List Functions

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

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

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

Recommendations

• The characterization of orders for regular functions 👍 👎
• First-order logic and first-order functions 👍 👎
• A generalization of functions of the first class 👍 👎
• First-Class Functions 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)