# Given start strings, find simplest DAG that constructs target strings by concatenation

Say we have a number of start strings (green) and a number of target strings (red). Two strings can always be concatenated to a new string which can then be arbitrarily often reused (two arrows in, (1,∞) arrows out). A string can also be concatenated with itself.

Is there an algorithm that can tell if this is the DAG that has the least number of nodes?

Is there an algorithm that gives a DAG that constructs the strings?

Is there an algorithm that gives the least complex (by number of nodes) DAG?

Does this problem have a name?

It seems that this is related to the https://en.wikipedia.org/wiki/Steiner_tree_problem (but it is not a minimal spanning tree, because the paths could be disjoint).

Someone pointed me to the addition sequence problem, which seems equivalent and is NP-complete: https://epubs.siam.org/doi/abs/10.1137/0210047

• In your example the starting strings form a disjoint alphabet. Is this always the case, or could the starting strings share characters (e.g. $BAB$ and $ABA$), or even share common prefix/suffixes (e.g. $AC$ and $ABA$)? – orlp Nov 16 '20 at 23:16
• @orlp The starting strings have no restrictions – 2080 Nov 16 '20 at 23:16