Uniform random generation of expressions respecting algebraic identities
Algorithms for the uniform random generation of a class of formal expressions are considered. This class contains arithmetical expressions, tree representations, algebraic expressions and program structures. A modification of the algorithm for context-free languages from \textit{T. Hickey} and \textit{J. Cohen} [SIAM J. Comput. 12, 645-655 (1983; Zbl 0524.68046)] is used. A parallelizable algorithm for a speed up in the generation time is constructed.
scientific article; zbMATH DE number 24899
scientific article