Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(generalized strings). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


University of Colorado

1. Char, Ian Guo-fan. Algorithmic Construction and Stochastic Analysis of Optimal Automata for Generalized Strings.

Degree: MS, 2018, University of Colorado

In many applications, the need arises to search a text for appearances of a given set of keywords. As an example, in bioinformatics one may wish to search a DNA sequence to find so-called <i>biological motifs</i>. A standard approach to this problem is to leverage a <i>deterministic finite automaton</i> – a graph structure which is traversed as letters of the text are read in. However, depending on the number and length of the keywords being sought in the text, the graph may be too large to fit in computer memory, making this approach fruitless. In this thesis, we first present a novel algorithm that, under the assumption that the keywords take the form of a so-called <i>generalized string</i>, constructs the minimal DFA recognizing those keywords. Importantly, the algorithm is iterative and allows one to build the automaton directly, without any use of buffer memory. Not only does this mean that the algorithm is efficient regarding memory consumption, but it also provides useful insight to help facilitate analysis for the size of such DFA. Using this new algorithm and pairing it with the assumption that the generalized strings are drawn at random from some class of probability distributions, we develop bounds on the size of the minimal automaton that are true with high probability. Furthermore, using synthetic data, we provide evidence that the size of the minimal automaton grows linearly in expectation for many cases. Advisors/Committee Members: Manuel E. Lladser, Jem Corcoran, Anne Dougherty.

Subjects/Keywords: aho-corasick automaton; biological motifs; deterministic finite automata; generalized strings; stochastic analysis; Applied Mathematics; Computer Sciences

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6th Edition):

Char, I. G. (2018). Algorithmic Construction and Stochastic Analysis of Optimal Automata for Generalized Strings. (Masters Thesis). University of Colorado. Retrieved from https://scholar.colorado.edu/appm_gradetds/115

Chicago Manual of Style (16th Edition):

Char, Ian Guo-fan. “Algorithmic Construction and Stochastic Analysis of Optimal Automata for Generalized Strings.” 2018. Masters Thesis, University of Colorado. Accessed March 06, 2021. https://scholar.colorado.edu/appm_gradetds/115.

MLA Handbook (7th Edition):

Char, Ian Guo-fan. “Algorithmic Construction and Stochastic Analysis of Optimal Automata for Generalized Strings.” 2018. Web. 06 Mar 2021.

Vancouver:

Char IG. Algorithmic Construction and Stochastic Analysis of Optimal Automata for Generalized Strings. [Internet] [Masters thesis]. University of Colorado; 2018. [cited 2021 Mar 06]. Available from: https://scholar.colorado.edu/appm_gradetds/115.

Council of Science Editors:

Char IG. Algorithmic Construction and Stochastic Analysis of Optimal Automata for Generalized Strings. [Masters Thesis]. University of Colorado; 2018. Available from: https://scholar.colorado.edu/appm_gradetds/115

.