Splicing semigroups of dominoes and DNA (Q1175793)

The authors define a semigroup of ``dominoes'' which are pairs of strings in some alphabet which match in their middle, and can join with other such dominoes where one string extends beyond the other. They prove several basic problems involving the semigroup of dominoes are undecidable but that for the special case of ``alphabetic dominoes'' in which the possible linkage of two strings depends only on the pairs of letters which are matched, not pairs of longer words, the associate language is regular, if the initial set is.