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 -