A1 Refereed original research article in a scientific journal
SPLICING SEMIGROUPS OF DOMINOES AND DNA
Authors: CULIK K, HARJU T
Publisher: ELSEVIER SCIENCE BV
Publication year: 1991
Journal: Discrete Applied Mathematics
Journal name in source: DISCRETE APPLIED MATHEMATICS
Journal acronym: DISCRETE APPL MATH
Volume: 31
Issue: 3
First page : 261
Last page: 277
Number of pages: 17
ISSN: 0166-218X
DOI: https://doi.org/10.1016/0166-218X(91)90054-Z
Abstract
We introduce semigroups of dominoes as a tool for working with sets of linked strings. In particular, we are interested in splicing semigroups of dominoes. In the special case of alphabetic (symbol-to-symbol linked) dominoes the splicing semigroups are essentially equivalent to the splicing systems introduced by Head to study informational macromolecules, specifically to study the effect of sets of restriction enzymes and ligase that allow DNA molecules to be cleaved and reassociated to produce further molecules. Our main result is that in the case of alphabetic dominoes the splicing semigroup generated from an initial regular set is again regular. This implies positive solution of two open problems stated by Head, namely the regularity of splicing systems and the decidability of their membership problem.
We introduce semigroups of dominoes as a tool for working with sets of linked strings. In particular, we are interested in splicing semigroups of dominoes. In the special case of alphabetic (symbol-to-symbol linked) dominoes the splicing semigroups are essentially equivalent to the splicing systems introduced by Head to study informational macromolecules, specifically to study the effect of sets of restriction enzymes and ligase that allow DNA molecules to be cleaved and reassociated to produce further molecules. Our main result is that in the case of alphabetic dominoes the splicing semigroup generated from an initial regular set is again regular. This implies positive solution of two open problems stated by Head, namely the regularity of splicing systems and the decidability of their membership problem.
UTU Research Portal