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

speech recognitioncomparison of strings of symbolspattern matching problem in a probabilistic frameworkprobability of a match

Mathematics Subject Classification ID

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

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

(11)

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

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)