String sets commutative under concatenation Given $A$ and $B$, string sets included in the Kleene closure of the same alphabet, say something about their nature (are they the same, or somehow interlinked by a simple set concatenation?) if $AB = BA$ (the invisible operator being set concatenation).
 A: Let $\Sigma$ be a finite alphabet. Given regular languages $A,B \subseteq \Sigma^{\ast}$ we want to solve $AB = BA$, which means every word $uv \in AB$ with $u \in A, v \in B$ has a prefix in $B$ and a suffix in $A$, i.e. we have $uv = yx$ for $y \in B$ and $x \in A$.
Now I guess your are looking for necessary and sufficient criteria on $A$ and $B$ such that the equation $AB = BA$ holds. I can only give you partial answers.
i) First note that if $A,B$ form submonoids, i.e. we have $A^2 \subseteq A$ and $B^2 \subseteq B$ and both contain the empty word, then
$$
 AB = BA \Leftrightarrow (AB)^2 \subseteq AB
$$
i.e. $AB$ forms itself a submonoid. For the proof note that if $AB = BA$ then $(AB)^2 = A^2B^2 \subseteq AB$, and conversely as $B \subseteq AB$ and $A \subseteq AB$ we have $BA \subseteq (AB)^2 \subseteq AB$, and for sets of words
we have $BA \subseteq AB$ iff $BA = AB$ (I give a proof below).
ii) For the more general case lets try to use Levi's lemma and for language $U,V \subseteq \Sigma^{\ast}$ set
$$
 U^{-1}V := \{ w \in \Sigma \mid \exists u \in U : uw \in V \} \quad 
 UV^{-1} := \{ w \in \Sigma \mid \exists v \in V : wv \in U \}
$$
i.e. words that remain if we take away initial segments from $U$ or suffixes from $V$. Than Levi's lemma states that
$$
 uv = xy \Leftrightarrow ( \{u\}^{-1}\{x\} \cap \{v\}\{y\}^{-1} ) \cup ( \{x\}^{-1}\{u\} \cap \{ y\} \{v\}^{-1} ) \ne \emptyset.
$$
So generalising we may set for $A,B \subseteq \Sigma^{\ast}$
$$
 L := A^{-1}B \cap AB^{-1}.
$$
Then we have that if $B \subseteq LA$ and $AL \subseteq A$ then $AB = BA$. For a proof suppose that $uv \in AB$ with $u \in A, v \in B$, and assume $v = wx$ with $x \in A, w \in L$. Then $uv = uwx$ and with $uw \in A$ we have $AB \subseteq BA$. Now this assumption is quite strong, and I do not think that a converse holds.
Note that I do not used regularity of $A$ and $B$, and I have no idea how to use it, beside maybe that $AB = BA$ is a decidable question then as we can construct automata for their concatenation and test if they accept the same language.
Appendix: For languages $A,B \subseteq \Sigma^{\ast}$ we have $AB \subseteq BA$ iff $AB = BA$. For each fixed $n$ in $AB$ and in $BA$ there are the same number of words of length $n$, as there is an easy bijection $uv \mapsto vu$ for $u\in A, v \in B$. So $AB \subset BA$ gives $AB \cap \Sigma^n \subseteq BA \cap \Sigma^n$ for each $n$, hence $AB \cap \Sigma^n = BA \cap \Sigma^n$. As these finite sets partition $AB$ and $BA$ the result follows.
A: Your question is related to famous problem formulated by Conway [1, p. 55 and 124] in 1971. Given a regular language $L$, is the largest language commuting with $L$ also regular?
However, in a famous breakthrough paper, Kunc [3] gave the most negative possible answer to Conway’s problem by showing that there exists a finite language $L$ such that the greatest solution of the equation $XL = LX$ is co-recursively enumerable complete.
This contrasts with the fact that the largest solution of the inequality $XK \subseteq LX$ is regular provided that the language $L$ is regular, as proved in [2].
[1] J. H. Conway, Regular Algebra and Finite Machines, Chapman and Hall, London, 1971.
[2] M. Kunc, Regular solutions of language inequalities and well quasi- orders. Theoret. Comput. Sci. 348(2–3) (2005) 277–293.
[3] M. Kunc, The power of commuting with finite sets of words, Theory Comput. Syst. 40,4 (2007), 521–551.
