Paper Info
Title
Modelling, simulating and verifying turing-powerful strand displacement systems
Abstract
We demonstrate how the DSD programming language can be used to design a DNA stack machine and to analyse its behaviour. Stack machines are of interest because they can efficiently simulate a Turing machine. We extend the semantics of the DSD language to support operations on DNA polymers and use our stack machine design to implement a non-trivial example: a ripple carry adder which can sum two binary numbers of arbitrary size. We use model checking to verify that the ripple carry adder executes correctly on a range of inputs. This provides the first opportunity to assess the correctness and kinetic properties of DNA strand displacement systems performing Turing-powerful symbolic computation.
Year
DOI
Venue
2011
10.1007/978-3-642-23638-9_12
DNA
Keywords
Field
DocType
machine design,dna strand displacement system,turing machine,dna polymers,turing-powerful strand displacement system,dsd language,turing-powerful symbolic computation,kinetic property,dsd programming language,binary number,arbitrary size,system performance,ripple carry adder,kinetics,model checking,programming language,symbolic computation
Pointer machine,Model checking,Adder,Computer science,Correctness,Symbolic computation,Algorithm,Turing machine,Turing,Stack machine
Conference
Volume
ISSN
Citations 
6937
0302-9743
13
PageRank 
References 
Authors
0.84
13
2
Name
Order
Citations
PageRank
Matthew R. Lakin17910.99
Andrew Phillips222717.50