I am basically only looking for a name of a problem so I can find information about it. A friend of mine explained it to me like this:

Given is a set of string variables $(x_1, \ldots, x_n)$, and a set of regular expressions $(r_1, \ldots, r_n)$ which constrain the string variables $x_i \in \mathbb{L}(r_i)$. Also given are two concatenations $c = x_{c_1} x_{c_2} \ldots x_{c_s}$ and $d = x_{d_1} x_{d_2} \ldots x_{d_t}$ over these string variables. The question now is: are there values for $x_1 \ldots x_n$ s.t. $c = d$?

As an example: Let $x_1, x_2, x_3$ be our string variables, and $a^*a, \ b^*b, \ (a|b) a^*$ our regular expressions respectively. Our concatenations are $c = x_1 x_2 x_1$ and $d = x_3 x_3$. Then $c=d$ is unsatisfiable. If we'd change the regular expression for $x_3$ to $(a|b)^*a$, then $c=d$ would be satisfiable.

Unfortunately, he only knows it as the 'String problem', which doesn't give too much information about it. Is that really it's name? Or how can I find more information about it?

  • $\begingroup$ I think that you want the constraints to be $x_i\in L(r_i)$, not $x_1\in L(r_i)$. $\endgroup$ – Brian M. Scott Oct 24 '11 at 10:21
  • $\begingroup$ This sounds like a "word problem". If you have a group or semigroup with a finite presentation, the word problem for that presentation asks for an algorithm for determining when two words over the set of generators are the same. Although, if this type of problem goes by the same name, good luck googling "word problem" :( $\endgroup$ – Bill Cook Oct 24 '11 at 10:46

After quite a bit of research I have found the answer: It's (similar to) the satisfiability problem for word equations.

The original problem is slightly different, but Makanin was the first one to prove this problem decidable and give an algorithm for it in 1977.

  • $\begingroup$ For a more modern (and free) presentation of the algorithm/result, one could look at Chapter 12 of Algebraic Combinatorics on Words. $\endgroup$ – Fizz Feb 6 '15 at 18:36
  • $\begingroup$ Note (from the aforementioned source) that Makanin's algorithm is EXPSPACE. In 1999 Plandowski came up with a different algorithm which is only PSPACE, but NEXPTIME. $\endgroup$ – Fizz Feb 7 '15 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.