A Linear Algorithm for the Random Sampling from Regular Languages

被引：1
作者：
Olivier Bernardi
Omer Giménez
机构：
[1] MIT,
[2] Universitat Politecnica de Catalunya,undefined
来源：
Algorithmica | 2012年 / 62卷
关键词：
Random sampling; Regular languages;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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(n2) 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.
引用
收藏
页码：130 / 145
页数：15
相关论文
共 24 条
  • [1] Barcucci E.(1999)Random generation of trees and other combinatorial objects Theor. Comp. Sci. 218 219-232
  • [2] Del Lungo A.(1999)ECO: a general methodology for the enumeration of combinatorial objects J. Differ. Equ. Appl. 5 435-490
  • [3] Pergola E.(1996)Génération aléatoire uniforme de mots de langages rationnels Theor. Comp. Sci. 159 43-63
  • [4] Barcucci E.(1999)Uniform random generation of decomposable structures using floating-point arithmetic Theor. Comp. Sci. 218 233-248
  • [5] Del Lungo A.(2004)Boltzmann samplers for the random generation of combinatorial structures Comb. Probab. Comput. 3 577-625
  • [6] Pergola E.(1994)A calculus for the random generation of labelled combinatorial structures Theor. Comp. Sci. 132 1-35
  • [7] Pinzani R.(2009)Uniform random sampling of planar graphs in linear time Random Struct. Algorithms 35 464-522
  • [8] Denise A.(1995)Random generation of words in an algebraic language in linear binary space Inf. Process. Lett. 54 229-233
  • [9] Denise A.(1983)Uniform random generation of strings in a context-free language SIAM J. Comput. 12 645-655
  • [10] Zimmermann P.(1994)Generating words in a context free language uniformly at random Inf. Process. Lett. 49 95-99
123