On the Solvability Problem for Restricted Classes of Word Equations
On the Solvability Problem for Restricted Classes of Word Equations
复制标题
关于限制类词方程的可解性问题
DOI：
10.1007/978-3-662-53132-7_25
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Markus L. Schmid
中科院分区：
文献类型：
--
作者：
F. Manea;Dirk Nowotka;Markus L. Schmid
研究了带正则约束和不带正则约束的受限字方程可解性问题的复杂性。对于一般的字方程，可解性问题仍然是$${{\mathsm{\mathsf{np}$$-Hard，即使两边的变量是有序的，对于具有正则约束的字方程，可解性问题仍然是$-Hard。另一方面，只有一个重复变量但有任意多个变量且两边至少有一个非重复变量的字方程可以在多项式时间内求解。
We investigate the complexity of the solvability problem for restricted classes of word equations with and without regular constraints. For general word equations, the solvability problem remains $${{\mathrm{\mathsf {NP}}}}$$-hard, even if the variables on both sides are ordered, and for word equations with regular constraints, the solvability problems remains $${{\mathrm{\mathsf {NP}}}}$$-hard for variable disjoint i.i¾?e., the two sides share no variables equations with two variables, only one of which is repeated. On the other hand, word equations with only one repeated variable but an arbitrary number of variables and at least one non-repeated variable on each side, can be solved in polynomial-time.