Publication details

Saarland University Computer Science

Simulating Boolean circuits by finite splicing

Katrin E. Erk

Proc. Congress on Evolutionary Computation (CEC '99), pp. 1279--1285, July 1999

As a computational model to be simulated in a DNA computing context, Boolean circuits are especially interesting because of their parallelism. Simulations in concrete biochemical computing settings have been given by [Ogihara/Ray 96] and [Amos/Dunne97]. In this paper, we show how to simulate Boolean circuits by finite splicing systems, an abstract model of enzymatic recombination. We argue that using an abstract model of DNA computation as a basis leads to simulations of greater clarity and generality. In our construction, the running time of the simulating system is proportional to the depth, and the use of material is proportional to the size of the Boolean circuit simulated. However, the rules of the simulating splicing system depend on the size of the Boolean circuit, but not on the connectives used.

Download PDF        Show BibTeX               


Login to edit


Webmaster, Wed Sep 16 10:47:00 2009