Counting of a Degenerate Word in Random Sequences

摘要

Overlap of words complicates the problem of word counting. The technique of the imbedded Markov chain(IMC) uses an enlarged state space to recover the Markovian property for the word counting problem. A degenerate wordrepresents multiple non-degenerate words. An efficient way to decompose a degenerate word according to its overlappingpattern for implementing IMC is proposed.