Stochastic analysis of minimal automata growth for generalized strings
DOI10.1007/s11009-019-09706-8zbMath1434.68240OpenAlexW2922335066WikidataQ128297604 ScholiaQ128297604MaRDI QIDQ2176399
Ian G. Char, Manuel E. Lladser
Publication date: 4 May 2020
Published in: Methodology and Computing in Applied Probability (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11009-019-09706-8
motifpolynomial growthminimizationdeterministic finite automatongeneralized stringAho-Corasick algorithm
Analysis of algorithms (68W40) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Construction of minimal deterministic finite automata from biological motifs
- The distribution of subword counts is usually normal
- Multiple pattern matching: a Markov chain approach
- On pattern frequency occurrences in a Markovian sequence
- On patterns in sequences of random events
- Compound Poisson approximation for Markov chains using Stein's method
- Motif statistics.
- Approximation of sojourn-times via maximal couplings: motif frequency distributions
- An Efficient Linear Pseudo-minimization Algorithm for Aho-Corasick Automata
- On probability generating functions for waiting time distributions of compound patterns in a sequence of multistate trials
- Improved compound Poisson approximation for the number of occurrences of any rare word family in a stationary markov chain
- Introduction to Computational Genomics
- Hidden word statistics
- Uniqueness of polynomial canonical representations
- Self-alignments in words and their applications
- Efficient string matching
- Distribution Theory of Runs: A Markov Chain Approach
- Markovian embeddings of general random strings
- Waiting time distributions of competing patterns in higher-order Markovian sequences
- Recurrent events in a Markov chain
This page was built for publication: Stochastic analysis of minimal automata growth for generalized strings