Splicing semigroups of dominoes and DNA. (English) Zbl 0747.20035

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.


20M35 Semigroups in automata theory, linguistics, etc.
92D20 Protein sequences, DNA sequences
68Q80 Cellular automata (computational aspects)
20M05 Free semigroups, generators and relations, word problems
Full Text: DOI


[1] Culik, K.; Harju, T., Dominoes over a free monoid, Theor. Comput. Sci., 18, 279-300 (1982) · Zbl 0509.68068
[2] Denninghoff, K. L.; Gatterdam, R. W., On the undecidability of splicing systems, Internat. J. Comput. Math., 27, 133-145 (1989)
[3] Head, T., Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors, Bull. Math. Biol., 49, 737-759 (1987) · Zbl 0655.92008
[4] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[5] Lewin, B., Genes III (1987), Wiley: Wiley New York
[6] Watson, J. D.; Tooze, J.; Kurtz, D. T., Recombinant DNA: A Short Course (1983), Freeman: Freeman New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.