Uniform random generation of expressions respecting algebraic identities (Q1179541)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Uniform random generation of expressions respecting algebraic identities |
scientific article |
Statements
Uniform random generation of expressions respecting algebraic identities (English)
0 references
26 June 1992
0 references
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.
0 references
uniform random generation
0 references
arithmetical expressions
0 references
tree representations
0 references
algebraic expressions
0 references
parallelizable algorithm
0 references
associative
0 references
commutative
0 references
simply generated families of trees
0 references
recognizable families of trees
0 references
enumeration problems
0 references
