University of North Florida. Department of Mathematics and Statistics
Maximality and Applications of Subword-Closed Languages
Abstract
dc:description.abstractCharacterizing languages D that are maximal with the property that D* ⊆ S⊗ is an important problem in formal language theory with applications to coding theory and DNA codewords. Given a finite set of words of a fixed length S, the constraint, we consider its subword closure, S⊗, the set of words whose subwords of that fixed length are all in the constraint. We investigate these maximal languages and present characterizations for them. These characterizations use strongly connected components of deterministic finite automata and lead to polynomial time algorithms for generating such languages. We prove that the subword closure S⊗ is strictly locally testable. Finally, we discuss applications to coding theory and encoding arbitrary blocks of information on DNA strands. This leads to very important applications in DNA codewords designed to obtain bond-free languages, which have been experimentally confirmed.
Degree
thesis:*- Name thesis:degree_name
- Master of Science in Mathematical Sciences (MS)
- Discipline thesis:degree_discipline
- Mathematics & Statistics
- Grantor
- University of North Florida. Department of Mathematics and Statistics
- Date dc:date.issued
- Summer
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Jones, Rhys Davis
- Jones, Rhys Davis, 1993-
- Advisors dc:contributor.advisor
-
- Genova, Daniela
- DeDeo, Michelle
- Lee, Jae-Ho
- Contributors dc:contributor
-
- Dr. Daniela Genova
- Dr. Michelle DeDeo
- Dr. Jae-Ho Lee
Subjects
dc:subject × 7- Thesis; University of North Florida; UNF; Dissertations
- Academic -- UNF -- Master of Science in Mathematical Science; Dissertations
- Academic -- UNF -- Mathematics; Finite State Automata; Regular Languages; Subword Closure; Involution Mappings; Strictly Locally Testable Languages; DNA Code Words
- Discrete Mathematics and Combinatorics
- Other Mathematics
- Theory and Algorithms
- Formal languages -- Mathematical models; Machine theory; Mathematics -- Data processing -- Testing; Coding theory -- Testing; Sequential machine theory; Algorithms -- Testing; Polynomials -- Testing
Rights
dc:rightsIdentifiers
dc:identifier.*- Repository record dc:identifier
- https://digitalcommons.unf.edu/etd/978