Uniform random generation of expressions respecting algebraic identities
type: Item
instance of: scholarly article
title: Uniform random generation of expressions respecting algebraic identities
zbMATH Open document ID: 0752.65002
DOI: 10.1007/BF02242022
published in: Computing
publication date: 1992-06-26T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65C10
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 24899
zbMATH Keywords: uniform random generation
zbMATH Keywords: arithmetical expressions
zbMATH Keywords: tree representations
zbMATH Keywords: algebraic expressions
zbMATH Keywords: parallelizable algorithm
zbMATH Keywords: associative
zbMATH Keywords: commutative
zbMATH Keywords: simply generated families of trees
zbMATH Keywords: recognizable families of trees
zbMATH Keywords: enumeration problems
author: Walter J. Gutjahr
reviewed by: Wilfried Grecksch
MaRDI profile type: Publication
cites work: Q4091421
cites work: Q3948568
cites work: Q3723577
cites work: Evaluation of Arithmetic Expressions with Algebraic Identities
cites work: The average height of binary trees and other simple trees
cites work: Q4711742
cites work: Q5682013
cites work: Uniform Random Generation of Strings in a Context-Free Language
cites work: On the Altitude of Nodes in Random Trees
cites work: Q4111065
cites work: Generating binary trees by transpositions
cites work: The Generation of Optimal Code for Arithmetic Expressions
cites work: Linear time tree codes
Recommended article: Q3943892
Recommended article: Algorithmically Random Universal Algebras
Recommended article: Uniformly distributed sequences in computer algebra or how to construct program generators of random numbers
Recommended article: Algorithms for generating random variables with a rational probability-generating function
Recommended article: Q3708858
Recommended article: Algebraic polynomials with non-identical random coefficients
Recommended article: The Generation of Arithmetical Identities.
Recommended article: Q4279227
Recommended article: Around random algebra
description: scientific article; zbMATH DE number 24899