# Searching name for string concatenation problem

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?

-
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