String matching: The ergodic case

DOI10.1214/AOP/1176989686MaRDI QIDQ1201167zbMATH OpenOpenAlexFDO

Authors Paul Shields

Publication date 17 January 1993

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1214/aop/1176989686

zbMATH Keywords

alphabetasymptotic growth rateDNA modelingdoubly infinite sequencesentropy boundergodic processesshift-invariant measurestationary finite-alphabet ergodic processstring matching

Mathematics Subject Classification ID

Strong limit theorems (60F15) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20)

Recommendations

• scientific article; zbMATH DE number 3963627
• An Erdős-Rényi law with shifts
• String matching bounds via coding
• Counts of long aligned word matches among random letter sequences
• Critical phenomena in sequence matching

Cited in

(9)

• String matching bounds via coding
• Longest common substring for random subshifts of finite type
• A note on the longest matching consecutive subsequence
• Fast string matching in stationary ergodic sources
• Rényi entropy and pattern matching for run-length encoded sequences
• String Matching: Communication, Circuits, and Learning.
• Waiting times: Positive and negative results on the Wyner-Ziv problem
• Two divergence-rate counterexamples
• Repetition and recurrence times: dual statements and summable mixing rates

This page was built for publication: String matching: The ergodic case

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