定理 1. 任意带Regex约束的Word Equation都可以转换为等价的Straight Line的带Regex约束的Word Equation

证明. 一个简单的编码过程：

对每一个等式\(t_1 = t_2\)（其中t是变量、常量、\(\varepsilon\)的拼接），将其替换为新的等式\(x = t_1 \#t_2\)，其中x是一个新变量，#不在原来的字母表内。同时为x添加一个regex约束：\(x \in L ((\Sigma^{\ast}) \#\backslash 1)\)。

显然，经过编码后，word equation满足straight line，且和原来的等式是等价的。

因为带正则约束的word equation是PS的，上述编码过程在多项式时间可以完成，因此：

推论 2. 带regex约束的straight line word equation的求解至少是PS的

实际上上述编码只用到了vsf regex的约束。因此即使是带vsf regex约束的word equation，也至少是PS的。