A Linear Algorithm for the Random Sampling from Regular Languages

作者：Bernardi Olivier; Gimenez Omer^*

来源：Algorithmica, 2012, 62(1-2): 130-145.

DOI：10.1007/s00453-010-9446-5

• Random sampling
• Regular languages

We present the first linear algorithm for the random sampling from regular languages. More precisely, for generating a uniformly random word of length n in a given regular language, our algorithm has worst-case space bit-complexity O(n) and mean time bit-complexity O(n). The previously best algorithm, due to Denise and Zimmermann (Theor. Comp. Sci. 218(2):233-248, 1999), has worst-case space bit-complexity O(n (2)) and mean time bit-complexity O(nlog (n)). The Denise et al. algorithm was obtained by performing a floating-point optimization on the general recursive method formalized by Nijenhuis and Wilf (and further developed by Flajolet, Zimmermann and Van Cutsem). Our algorithm combines the floating-point optimization with a new divide-and-conquer scheme.

• 出版日期2012-2