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-. 507.
https://stars.library.ucf.edu/etd2020/507