The Library
Regular and first-order list functions
Tools
Tools
Tools
Bojanczyk, Mikolaj, Daviaud, Laure and Krishna, Shankara Narayanan (2018) Regular and first-order list functions. In: LICS 2018 : 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, Oxford, United Kingdom, 9-12 Jul 2018. Published in: Lecture Notes in Computer Science doi:10.1145/3209108.3209163 ISSN 0302-9743.
|
PDF
WRAP-regular-first-order-list-functions-Daviaud-2018.pdf - Accepted Version - Requires a PDF viewer. Download (5Mb) | Preview |
Official URL: https://doi.org/10.1145/3209108.3209163
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
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | List processing (Electronic computers), Transducers, Robots | |||||||||
| Journal or Publication Title: | Lecture Notes in Computer Science | |||||||||
| Publisher: | Springer | |||||||||
| ISSN: | 0302-9743 | |||||||||
| Official Date: | 31 March 2018 | |||||||||
| Dates: |
|
|||||||||
| DOI: | 10.1145/3209108.3209163 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| Date of first compliant deposit: | 10 May 2018 | |||||||||
| Date of first compliant Open Access: | 10 May 2018 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | LICS 2018 : 33rd Annual ACM/IEEE Symposium on Logic in Computer Science | |||||||||
| Type of Event: | Other | |||||||||
| Location of Event: | Oxford, United Kingdom | |||||||||
| Date(s) of Event: | 9-12 Jul 2018 | |||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
