A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
SPLICING SEMIGROUPS OF DOMINOES AND DNA
Tekijät: CULIK K, HARJU T
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 1991
Lehti:: Discrete Applied Mathematics
Tietokannassa oleva lehden nimi: DISCRETE APPLIED MATHEMATICS
Lehden akronyymi: DISCRETE APPL MATH
Vuosikerta: 31
Numero: 3
Aloitussivu: 261
Lopetussivu: 277
Sivujen määrä: 17
ISSN: 0166-218X
DOI: https://doi.org/10.1016/0166-218X(91)90054-Z
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali