In this work we study some probabilistic models for the random generation of words over a given alphabet
used in the literature in connection with pattern statistics.
Our goal is to compare models based on Markovian processes (where the occurrence of a symbol in a given position
only depends on a finite number of previous occurrences) and the stochastic models that
can generate a word of given length from a regular language under uniform distribution.
We present some results that show the differences...
We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time -NAuxPDA with polynomially bounded ambiguity.
We prove that a word of length from a finitely
ambiguous context-free language can be generated at random under
uniform distribution in (
log ) time by a probabilistic random access machine assuming a logarithmic cost criterion.
We also show that the same problem can be solved in polynomial
time for every language accepted by a polynomial time -NAuxPDA
with polynomially bounded ambiguity.
Download Results (CSV)