Regular and First-Order List Functions

DOI10.1145/3209108.3209163MaRDI QIDQ5145284zbMATHOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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
• scientific article; zbMATH DE number 1678386
• The characterization of orders for regular functions
• scientific article; zbMATH DE number 3884443
• A generalization of functions of the first class

Cited in

(4)

• String-to-string interpretations with polynomial-size output
• Transducers of polynomial growth
• Sequentiality of string-to-context transducers
• The many facets of string transducers (invited talk)

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)