Uniform random generation of words of rational languages

DOI10.1016/0304-3975(95)00200-6zbMath0872.68086OpenAlexW2001960495MaRDI QIDQ1351211

Alain Denise

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00200-6

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Watermelon uniform random generation with applications ⋮ Average Value and Variance of Pattern Statistics in Rational Models ⋮ A linear algorithm for the random sampling from regular languages ⋮ Frequency of symbol occurrences in bicomponent stochastic models ⋮ Uniform random generation of decomposable structures using floating-point arithmetic ⋮ Probabilistic models for pattern statistics ⋮ On computing the coefficients of bivariate holonomic formal series

Uses Software

• Gaia

Cites Work

• Random generation of words in an algebraic language in linear binary space
• A method and two algorithms on the theory of partitions
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• Generating words in a context-free language uniformly at random
• A calculus for the random generation of labelled combinatorial structures
• The random generation of underdiagonal walks
• On the computational power of pushdown automata
• Uniform Random Generation of Strings in a Context-Free Language
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Uniform random generation of words of rational languages