Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata

DOI10.1239/jap/1208358964zbMath1142.65010MaRDI QIDQ5459921

Gregory Nuel

Publication date: 30 April 2008

Published in: Journal of Applied Probability (Search for Journal in Brave)

zbMATH Keywords

algorithmsnumerical exampleslanguageexact distributionMarkov chain embeddingregular expressionstructured motifpatterns in random textsPROSITE signature

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Pattern recognition, speech recognition (68T10) Numerical analysis or methods applied to Markov chains (65C40) Computing methodologies for text processing; mathematical typography (68U15)

Related Items (17)

Analytic combinatorics for computing seeding probabilities ⋮ On longest consecutive patterns in Markov chains ⋮ Recursive equations in finite Markov chain imbedding ⋮ Faster exact distributions of pattern statistics through sequential elimination of states ⋮ Minimal auxiliary Markov chains through sequential elimination of states ⋮ A new method of approximating the probability of matching common words in multiple random sequences ⋮ Sparse approaches for the exact distribution of patterns in long state sequences generated by a Markov source ⋮ Large deviation properties for patterns ⋮ Distributions associated with \((k_1,k_2)\) events on semi-Markov binary trials ⋮ An algorithm to compute the character access count distribution for pattern matching algorithms ⋮ Occurrence of structured motifs in random sequences: arbitrary number of boxes ⋮ Moments of the count of a regular expression in a heterogeneous random sequence ⋮ On the First k Moments of the Random Count of a Pattern in a Multistate Sequence Generated by a Markov Source ⋮ Large deviations and full Edgeworth expansions for finite Markov chains with applications to the analysis of genomic sequences ⋮ Distribution of Clump Statistics for a Collection of Words ⋮ Distributions of pattern statistics in sparse Markov models ⋮ Asymptotic properties of words in semi-Markov sequences

Uses Software

• ARPACK
• SPatt

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Waiting times for clumps of patterns and for structured motifs in random sequences
• Waiting time and complexity for matching patterns with automata
• A martingale approach to the study of occurrence of sequence patterns in repeated experiments
• String overlaps, pattern matching, and nontransitive games
• Explicit distributional results in pattern formation
• Exact distribution of the distances between any occurrences of a set of words
• Motif statistics.
• Waiting times for patterns in a sequence of multistate trials
• On probability generating functions for waiting time distributions of compound patterns in a sequence of multistate trials
• The Occurrence of Sequence Patterns in Repeated Dependent Experiments
• Cumulative distribution function of a geometric Poisson distribution
• Markov renewal processes, counters and repeated sequences in Markov chains
• Explicit Distributional Results In Pattern Formation II
• Exact distribution of word occurrences in a random sequence of letters
• Distribution Theory of Runs: A Markov Chain Approach
• On Runs and Longest Run Tests: A Method of Finite Markov Chain Imbedding
• ARPACK Users' Guide
• Joint distributions of successes, failures and patterns in enumeration problems
• On some waiting time problems
• The intersite distances between pattern occurrences in strings generated by general discrete- and continuous-time models: an algorithmic approach
• Numerical Solutions for Patterns Statistics on Markov Chains
• Gambling Teams and Waiting Times for Patterns in Two-State Markov Chains

This page was built for publication: Pattern Markov Chains: Optimal Markov Chain Embedding Through Deterministic Finite Automata