I'm currently in need of the inverse operation of the concatenation of 2 regular languages.
Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is the smallest language that fulfills the equation (which implies $\forall w \in B: A \cdot (B \setminus \{w\}) \subset C$).
The smallest-language requirement is necessary for my practical application, but I believe it's also necessary to make $B$ unique.
Special cases:
- $C = \varnothing \implies B = \varnothing$
- $A = C \neq \varnothing \implies B = \{\epsilon\}$
- $\epsilon \in A \implies B \subseteq C$
Notes:
- Whether the left or right operant is unknown doesn't matter. By reversing both side of the equation, we get $B^R \cdot A^R = C^R$. So a solution that can find $A$ can also find $B$ and vise versa.
- $B$ is trivially unique for $|B|<2$.
Open questions:
- Is $B$ unique in general? (I believe it is.)
- Is $B$ a regular language?
