Back to search

University of North Florida. Department of Mathematics and Statistics

Maximality and Applications of Subword-Closed Languages

Abstract

dc:description.abstract

Characterizing 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

Rights

dc:rights

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.unf.edu/etd/978

Chain of custody

source
Harvested from
University of North Florida
Base URL
digitalcommons.unf.edu/do/oai/
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Jones, Rhys Davis; Jones, Rhys Davis, 1993-. Maximality and Applications of Subword-Closed Languages. University of North Florida. Department of Mathematics and Statistics, https://digitalcommons.unf.edu/etd/978