Minimal Markov chain embeddings of pattern problems
Manuel E. Lladser · 2007
The Markov chain embedding technique is commonly used to study the distribution of statistics associated with regular patterns (i.e. set of strings described by a regular expression) in random strings. In this extended abstract, we formalize the concept Markov chain embedding for random strings produced by a possibly non-stationary Markov source. A notion of memory conveyed by the states of a deterministic finite automaton is introduced. This notion is used to characterize the smallest state-space size Markov chain required to specify the distribution of the count statistic of a given regular pattern. The research finds applications in problems associated with regular patterns in random strings that demand exponentially large state spaces.