Stochastic Analysis of Minimal Automata Growth for Generalized Strings

Ian G. Char and Manuel E. Lladser ()
Additional contact information
Ian G. Char: University of Colorado
Manuel E. Lladser: University of Colorado

Methodology and Computing in Applied Probability, 2020, vol. 22, issue 1, 329-347

Abstract: Abstract Generalized strings describe various biological motifs that arise in molecular and computational biology. In this manuscript, we introduce an alternative but efficient algorithm to construct the minimal deterministic finite automaton (DFA) associated with any generalized string. We exploit this construction to characterize the typical growth of the minimal DFA (i.e., with the least number of states) associated with a random generalized string of increasing length. Even though the worst-case growth may be exponential, we characterize a point in the construction of the minimal DFA when it starts to grow linearly and conclude it has at most a polynomial number of states with asymptotically certain probability. We conjecture that this number is linear.

Keywords: Aho-Corasick algorithm; Deterministic finite automaton; Generalized string; Minimization; Motif; Polynomial growth; 68Q25; 68Q45; 68Q87; 68W40 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11009-019-09706-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:22:y:2020:i:1:d:10.1007_s11009-019-09706-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-019-09706-8

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().