ICALP conference website banner

Article accepted at ICALP 2023

Paper at 50th ICALP conference

We are glad to share that our recent combinatorial work on sets of periods in strings have been accepted for publication at the 50th annual EATCS International Colloquium on Automata, Languages and Programming, also know as ICALP 2023.

This work closes a long standing conjecture stated by Leonid J. Guibas and Andrew Odlyzko in a seminal article in the Journal of Combinatorial Theory, A in 1981 (<10.1016/0097-3165(81)90038-8>). The conjecture is about the number of distinct set of periods in finite words in function of the word length n (see the page corresponding to this sequence of integers from the Encyclopedia of Integer Sequences). This number is also the number of distinct autocorrelations of binary words of length n.

Our preprint entitled Convergence of the number of period sets in strings (2022) is available on ArXiv here. It follows from the work of two talented PhD students: Michelle Sweering from CWI in Amsterdam, and Pengfei Wang at the LIRMM, CNRS and Montpellier University, France. involves the

ICALP stands as one of most notorious scientific event on Theoretical Computer Science. The acceptance rate is about 30% this year. Check out the list of accepted paper here.

Eric Rivals
CNRS Research Director in Computer Science and Bioinformatics

My research interests include string algorithms, bioinformatics, genomics.