"Two Computational Problems on String Rewriting Systems" by Wei Du

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.

Download

Share

COinS