Two Computational Problems on String Rewriting Systems

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.