Matching strings in encoded sequences
From MaRDI portal
Abstract: We investigate the longest common substring problem for encoded sequences and its asymptotic behaviour. The main result is a strong law of large numbers for a re-scaled version of this quantity, which presents an explicit relation with the R'enyi entropy of the source. We apply this result to the zero-inflated contamination model and the stochastic scrabble. In the case of dynamical systems, this problem is equivalent to the shortest distance between two observed orbits and its limiting relationship with the correlation dimension of the pushforward measure. An extension to the shortest distance between orbits for random dynamical systems is also provided.
Recommendations
- Rényi entropy and pattern matching for run-length encoded sequences
- Longest common substring for random subshifts of finite type
- On the shortest distance between orbits and the longest common substring problem
- Critical phenomena in sequence matching
- Maximal length of common words among random letter sequences
Cites work
- scientific article; zbMATH DE number 1516956 (Why is no real title available?)
- scientific article; zbMATH DE number 918233 (Why is no real title available?)
- A Phase Transition for the Distribution of Matching Blocks
- A suboptimal lossy data compression based on approximate pattern matching
- AN INTRODUCTION TO QUANTITATIVE POINCARÉ RECURRENCE IN DYNAMICAL SYSTEMS
- An Erdős-Rényi law with shifts
- Critical phenomena for sequence matching with scoring
- Entropy and data compression schemes
- Entry and return times distribution
- Exponential decay of correlations for randomly chosen hyperbolic toral automorphisms
- From the divergence between two measures to the shortest path between two observables
- Hitting time statistics for observations of dynamical systems
- Inequalities for the occurrence times of rare events in mixing processes. The state of the art
- Information theory and coding by example
- Large deviations for short recurrence
- Laws of rare events for deterministic and random dynamical systems
- Limit distribution of maximal non-aligned two-sequence segmental score
- Longest common substring for random subshifts of finite type
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- More on recurrence and waiting times
- Nonparametric entropy estimation for stationary processes and random fields, with applications to English text
- On compound Poisson approximation for sequence matching
- On the shortest distance between orbits and the longest common substring problem
- On the spectra of randomly perturbed expanding maps
- Poincaré recurrence for observations
- Pointwise dimensions for Poincaré recurrences associated with maps and special flows
- Quantitative recurrence results
- Random perturbations of stochastic processes with unbounded variable length memory
- Recurrence for random dynamical systems
- Recurrence rate in rapidly mixing dynamical systems
- Recurrence, dimensions, and Lyapunov exponents.
- Return times in a process generated by a typical partition
- Rényi Entropies and Large Deviations for the First Match Function
- Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression
- Stochastic scrabble: large deviations for sequences with scores
- Stochastically perturbed chains of variable memory
- The Rényi entropy function and the large deviation of short return times
- The Shortest Possible Return Time of <inline-formula> <tex-math notation="LaTeX">$\beta$ </tex-math> </inline-formula>-Mixing Processes
- The asymptotics of waiting times between stationary processes, allowing distortion
- The distribution of the short-return function
Cited in
(8)- Common substring with shifts in \(b\)-ary expansions
- Sequence matching with binary codes
- Longest common substring for random subshifts of finite type
- Matching of observations of dynamical systems, with applications to sequence matching
- Minimal distance between random orbits
- Shortest distance between multiple orbits and generalized fractal dimensions
- On the shortest distance between orbits and the longest common substring problem
- Rényi entropy and pattern matching for run-length encoded sequences
This page was built for publication: Matching strings in encoded sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174991)
