Date of Award
Spring 2025
Embargo Period
5-11-2025
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
College/School/Department
Department of Computer Science
Program
Computer Science
First Advisor
Paliath Narendran
Committee Members
Paliath Narendran, Chinwe Ekenna, Abram Magner, Michael Rusinowitch
Keywords
string-rewriting systems, forward-closed, convergent, recursive path ordering, NP-complete
Subject Categories
Computer Sciences | Theory and Algorithms
Abstract
String rewriting systems are widely used computational models in theoretical computer science research such as artificial intelligence, software and hardware verification, and symbolic cryptographic protocol analysis. In this dissertation, we investigate two interesting problems concerning these systems, namely the common left multiplier problem and the SYMBOL-ORDER problem.
First, we consider the common left multiplier problem for forward-closed convergent string rewriting systems. The task is to discover, given two distinct strings α and β, a target string W such that W α and W β will be equivalent with respect to the provided forward-closed convergent string rewriting system. We describe an algorithm for this problem and prove that it runs in polynomial time.
Next, we present the SYMBOL-ORDER problem, which is to orient an input string rewriting system using recursive path ordering (RPO) such that every left hand side is higher than the right hand side for each rule. We prove this problem is NP-complete and derived some consequences for single ground rule term rewriting systems. In addition, we show a symbol ordering can be found in polynomial time when the number of rules in the string rewriting system is fixed.
License
This work is licensed under the University at Albany Standard Author Agreement.
Recommended Citation
Du, Wei, "Two Computational Problems on String Rewriting Systems" (2025). Electronic Theses & Dissertations (2024 - present). 228.
https://scholarsarchive.library.albany.edu/etd/228
