This volume presents the proceedings from the third DIMACS workshop on "DNA Based Computers" held at the University of Pennsylvania (Philadelphia). The workshop was part of the Special Year on Molecular Biology and the Special Year on DNA Computing. The focus of this proceedings volume is on the multidisciplinary nature of the workshop with emphasis on the interaction between biology and biochemistry on one hand and computer science and mathematics on the other.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1-7 were co-published with the Association for Computer Machinery (ACM).

Readership

Graduate students and research mathematicians working in computer science.

Table of Contents

• J. G. Wetmur -- Physical chemistry of nucleic acid hybridization
• A. J. Hartemink and D. K. Gifford -- Thermodynamic simulation of deoxyoligonucleotide hybridization for DNA computation
• J. Khodor and D. K. Gifford -- The efficiency of sequence-specific separation of DNA mixtures for biological computing
• J. Chen and D. H. Wood -- A new DNA separation technique with a low error rate
• M. Hagiya, M. Arita, D. Kiga, K. Sakamoto, and S. Yokoyama -- Towards parallel evaluation and learning of Boolean \(\mu\)-formulas with molecules
• E. Laun and K. J. Reddy -- Wet splicing systems
• F. Guarnieri, M. Orlian, and C. Bancroft -- Parallel operations in DNA-based computation
• A. S. Fraenkel -- Protein folding, spin glass and computational complexity
• N. Jonoska, S. A. Karl, and M. Saito -- Creating 3-dimensional graph structures with DNA
• Y. Gao, M. Garzon, R. C. Murphy, J. A. Rose, R. Deaton, D. R. Franceschetti, and S. E. Stevens, Jr. -- DNA implementation of nondeterminism
• V. Gupta, S. Parthasarathy, and M. J. Zaki -- Arithmetic and logic operations with DNA
• L. F. Landweber, R. J. Lipton, and M. O. Rabin -- DNA\({^2}\)DNA computations: A potential "killer app?"
• A. D. Ellington, M. P. Robertson, K. D. James, and J. C. Cox -- Strategies for DNA computing
• T. L. Eng and B. M. Serridge -- A surface-based DNA algorithm for minimal set cover
• N. Morimoto, M. Arita, and A. Suyama -- Solid phase DNA solution to the Hamiltonian path problem
• B. Fu and R. Beigel -- On molecular approximation algorithms for NP optimization problem
• J. H. Reif -- Local parallel biomolecular computation
• M. Ogihara and A. Ray -- DNA-based parallel computation by "counting"
• A. J. Blumberg -- Parallel computation on a DNA substrate
• M. Conrad and K.-P. Zauner -- Design for a DNA conformational processor
• T. L. Eng -- Linear DNA self-assembly with hairpins generates linear context-free grammars
• R. Freund, Gh. Păun, G. Rozenberg, and A. Salomaa -- Watson-Crick finite automata
• L. Kari, G. Păun, G. Thierrin, and S. Yu -- At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems
• T. Yokomori and S. Kobayashi -- DNA-EC: A model of DNA-computing based on equality checking
• Y. Sakakibara and C. Ferretti -- Splicing on tree-like structures