City Research Online

Regular and First Order List Functions

Bojanczyk, M., Daviaud, L. and Narayanan, K. S. (2018). Regular and First Order List Functions. In: LICS '18 Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. LICS, 2018. (pp. 125-134). New York, NY: ACM. ISBN 978-1-4503-5583-4

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.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © {Bojanczyk, M., Daviaud, L., & Krishna, S. | ACM} {2018}. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in LICS '18 Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, http://dx.doi.org/10.1145/3209108.3209163.
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Mathematics, Computer Science & Engineering > Computer Science
URI: http://openaccess.city.ac.uk/id/eprint/21288
[img]
Preview
Text - Accepted Version
Download (6MB) | Preview

Export

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login