Back to Search
Start Over
Construction of minimal deterministic finite automata from biological motifs
- Source :
- Theoretical Computer Science. 412(8-10):922-930
- Publication Year :
- 2011
- Publisher :
- Elsevier BV, 2011.
-
Abstract
- Deterministic finite automata (DFAs) are constructed for various purposes in computational biology. Little attention, however, has been given to the efficient construction of minimal DFAs. In this article, we define simple non-deterministic finite automata (NFAs) and prove that the standard subset construction transforms NFAs of this type into minimal DFAs. Furthermore, we show how simple NFAs can be constructed from two types of pattern popular in bioinformatics, namely (sets of) generalized strings and (generalized) strings with a Hamming neighborhood.
- Subjects :
- Discrete mathematics
Nested word
Theoretical computer science
General Computer Science
Powerset construction
Minimization
Generalized string
Theoretical Computer Science
Consensus string
Deterministic finite automaton
DFA minimization
Deterministic automaton
Automata theory
Quantum finite automata
Motif
Nondeterministic finite automaton
Computer Science::Formal Languages and Automata Theory
Mathematics
Computer Science(all)
Subjects
Details
- ISSN :
- 03043975
- Volume :
- 412
- Issue :
- 8-10
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....b26bc06577348973f1ee69febf3c66ac
- Full Text :
- https://doi.org/10.1016/j.tcs.2010.12.003