Regular and first-order list functions

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:	http://www.scopus.com/inward/record.url?...
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