A finer reparameterisation theorem for MSO and FO queries on strings

Lê Thà nh Dũng Nguyên, Paweł Parys

We show a theorem on monadic second-order k-ary queries on finite words. It may be illustrated by the following example: if the number of results of a query on binary strings is O(…