Abstract
This dissertation presents novel algorithms and conditional lower bounds for a collection of string and text-compression-related problems. These results are unified under the theme of ordering constraint satisfaction. Utilizing the connections to ordering constraint satisfaction, we provide hardness results and algorithms for the following: recognizing a type of labeled graph amenable to text-indexing known as Wheeler graphs, minimizing the number of maximal unary substrings occurring in the Burrows-Wheeler Transformation of a text, minimizing the number of factors occurring in the Lyndon factorization of a text, and finding an optimal reference string for relative Lempel-Ziv encoding.
Notes
If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu
Graduation Date
2021
Semester
Spring
Advisor
Valliyil Thankachan, Sharma
Degree
Doctor of Philosophy (Ph.D.)
College
College of Engineering and Computer Science
Department
Computer Science
Degree Program
Computer Science
Format
application/pdf
Identifier
CFE0008478; DP0024154
URL
https://purls.library.ucf.edu/go/DP0024154
Language
English
Release Date
May 2021
Length of Campus-only Access
None
Access Status
Doctoral Dissertation (Open Access)
STARS Citation
Gibney, Daniel, "Algorithms and Lower Bounds for Ordering Problems on Strings" (2021). Electronic Theses and Dissertations, 2020-2023. 507.
https://stars.library.ucf.edu/etd2020/507