Waiting time and complexity for matching patterns with automata

DOI10.1016/S0020-0190(03)00271-0zbMath1161.68760OpenAlexW1980260642WikidataQ61677956 ScholiaQ61677956MaRDI QIDQ1014407

Valeri T. Stefanov, Maxime Crochemore

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(03)00271-0

zbMATH Keywords

algorithmsstopping timeMarkov chainformal languagesstring matching algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Pattern recognition, speech recognition (68T10)

Related Items

Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source ⋮ On the First k Moments of the Random Count of a Pattern in a Multistate Sequence Generated by a Markov Source ⋮ Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata

Cites Work

• Unnamed Item
• Unnamed Item
• On Simon's string searching algorithm
• Explicit distributional results in pattern formation
• A unified approach to word occurrence probabilities
• Conditionality resolutions
• Fast Pattern Matching in Strings
• Explicit Distributional Results In Pattern Formation II