Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
I think that you want the constraints to be $x_i\in L(r_i)$, not $x_1\in L(r_i)$. – Brian M. Scott Oct 24 '11 at 10:21
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" :( – Bill Cook Oct 24 '11 at 10:46
up vote 2 down vote accepted

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.

share|cite|improve this answer
For a more modern (and free) presentation of the algorithm/result, one could look at Chapter 12 of Algebraic Combinatorics on Words. – Fizz Feb 6 '15 at 18:36
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. – Fizz Feb 7 '15 at 2:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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