Waiting time and complexity for matching patterns with automata

✍ Scribed by M. Crochemore; V.T. Stefanov

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 105 KB
• Volume: 87
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(03)00271-0

✦ Synopsis

The paper shows how to compute exactly expectations, standard deviations, and cumulative probabilities of the searching times of string-matching algorithms based on the use of automata. This is derived from a methodology based on viewing the underlying Markov chains as exponential families and applying recent results on them.