A probabilistic analysis of a pattern matching problem

DOI10.1002/RSA.3240040206MaRDI QIDQ4696228zbMATH OpenOpenAlexFDO

Authors Wojciech Szpankowski, Mikhail J. Atallah, Philippe Jacquet

Publication date 29 June 1993

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240040206

zbMATH Keywords

comparison of strings of symbolspattern matching problem in a probabilistic frameworkprobability of a matchspeech recognition

Mathematics Subject Classification ID

Combinatorial probability (60C05) Limit theorems in probability theory (60F99) Data structures (68P05)

Recommendations

• Pattern matching between two non-aligned random sequences
• scientific article; zbMATH DE number 840348
• scientific article; zbMATH DE number 1984547
• Pattern Matching Statistics on Correlated Sources
• Fast string matching by using probabilities: on an optimal mismatch variant of Horspool's algorithm

Cites work

• scientific article; zbMATH DE number 41472 (Why is no real title available?)
• scientific article; zbMATH DE number 3592801 (Why is no real title available?)
• Non-negative matrices and Markov chains.
• Probability approximations via the Poisson clumping heuristic

Cited in

(12)

• Pattern matching between two non-aligned random sequences
• String matching bounds via coding
• A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm
• Pattern Matching Statistics on Correlated Sources
• scientific article; zbMATH DE number 1984547 (Why is no real title available?)
• The asymptotics of string matching probabilities for Gaussian random sequences
• Combinational optimization problems for which almost every algorithm is asymptotically optimal
• A Probabilistic Analysis of a String Editing Problem and its Variations
• String Matching for the Novice
• scientific article; zbMATH DE number 840348 (Why is no real title available?)
• scientific article; zbMATH DE number 7756108 (Why is no real title available?)
• String matching and 1d lattice gases

This page was built for publication: A probabilistic analysis of a pattern matching problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4696228)