$S$ is the set of words generated by an alphabet. $A\subset S$ , $x\in S$. How to find if $x$ is generated by concatenating elements of $A$?

Question

I am looking for references in relation to this problem. The name of the problem, texts or papers, efficient algorithms, and calculators.

Example:

$S$= the set of all finite binary strings, $A$= a finite subset of $S$, $x$= a particular finite binary string. Determine if $x$ can be obtained by concatenating elements of $A$ (repetition allowed).

Of course one can do brute force. Calculate $A^n$ and check, keeping branches that overlap with $x$. Are there more efficient algorithms?

Answer 1

Partial answer:

For your example - you can build a non-deterministic FSM in the spirit of Aho-Corasick algorithm (transitions = elements of $A$), and feed $x$ to that FSM to get an answer.

However, this approach does not generalize well to an arbitrary semigroup/monoid/group.