Uniform random generation of expressions respecting algebraic identities

DOI10.1007/BF02242022zbMath0752.65002MaRDI QIDQ1179541

Walter J. Gutjahr

Publication date: 26 June 1992

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

enumeration problemsassociativecommutativeuniform random generationtree representationsalgebraic expressionssimply generated families of treesarithmetical expressionsparallelizable algorithmrecognizable families of trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Random number generation in numerical analysis (65C10) Distributed algorithms (68W15)

Related Items

Simplifying regular expressions further ⋮ An improved algorithm for finding minimum-risk 3-state-device networks

Cites Work

• Linear time tree codes
• The average height of binary trees and other simple trees
• Uniform Random Generation of Strings in a Context-Free Language
• Generating binary trees by transpositions
• Evaluation of Arithmetic Expressions with Algebraic Identities
• On the Altitude of Nodes in Random Trees
• The Generation of Optimal Code for Arithmetic Expressions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item