Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics

DOI10.1007/978-3-540-69068-9_11zbMath1143.68440OpenAlexW2139817324MaRDI QIDQ3506945

Sven Rahmann, Tobias Marschall

Publication date: 17 June 2008

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69068-9_11

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational methods for problems pertaining to biology (92-08)

Related Items (10)

Set intersection and sequence matching with mismatch counting ⋮ Faster exact distributions of pattern statistics through sequential elimination of states ⋮ Minimal auxiliary Markov chains through sequential elimination of states ⋮ Construction of minimal deterministic finite automata from biological motifs ⋮ Optimal pattern matching algorithms ⋮ An algorithm to compute the character access count distribution for pattern matching algorithms ⋮ Designing optimal- and fast-on-average pattern matching algorithms ⋮ Moments of the count of a regular expression in a heterogeneous random sequence ⋮ Distribution of Clump Statistics for a Collection of Words ⋮ Distributions of pattern statistics in sparse Markov models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Construction of Aho Corasick automaton in linear time for integer alphabets
• Multiple pattern matching: a Markov chain approach
• A unified approach to word occurrence probabilities
• Re-describing an algorithm by Hopcroft
• Motif statistics.
• Efficient string matching
• On the Power of Profiles for Transcription Factor Binding Site Detection

This page was built for publication: Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics