TY - GEN

T1 - Regular and first-order list functions

AU - Bojańczyk, Mikołaj

AU - Daviaud, Laure

AU - Krishna, Shankara Narayanan

N1 - 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.

PY - 2018/7/9

Y1 - 2018/7/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85051107094&partnerID=8YFLogxK

U2 - 10.1145/3209108.3209163

DO - 10.1145/3209108.3209163

M3 - Conference contribution

AN - SCOPUS:85051107094

T3 - Proceedings - Symposium on Logic in Computer Science

SP - 125

EP - 134

BT - Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018

PB - The Institute of Electrical and Electronics Engineers (IEEE)

T2 - 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018

Y2 - 9 July 2018 through 12 July 2018

ER -