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.

String concatenation DAG

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

  • $\begingroup$ 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$)? $\endgroup$ – orlp Nov 16 '20 at 23:16
  • $\begingroup$ @orlp The starting strings have no restrictions $\endgroup$ – 2080 Nov 16 '20 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.