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