Bojańczyk, Mikołaj, Daviaud, Laure and Krishna, Shankara Narayanan (2018) Regular and first-order list functions. In: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018. Proceedings - Symposium on Logic in Computer Science . The Institute of Electrical and Electronics Engineers (IEEE), GBR, pp. 125-134. ISBN 9781450355834
Full text not available from this repository.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: | Book Section |
---|---|
Additional Information: | Funding Information: This research has been supported by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme (ERC consolidator grant LIPA, agreement no. 683080) and the EPSRC grant EP/P020992/1 (Solving Parity Games in Theory and Practice). Publisher Copyright: © 2018 ACM. |
Uncontrolled Keywords: | software,mathematics(all) ,/dk/atira/pure/subjectarea/asjc/1700/1712 |
Related URLs: | |
Depositing User: | LivePure Connector |
Date Deposited: | 08 Jun 2023 14:30 |
Last Modified: | 08 Jun 2023 14:30 |
URI: | https://ueaeprints.uea.ac.uk/id/eprint/92341 |
DOI: | 10.1145/3209108.3209163 |
Actions (login required)
![]() |
View Item |