The computational power of Benenson automata

DOI10.1016/j.tcs.2005.07.027zbMath1079.68055DBLPjournals/tcs/SoloveichikW05OpenAlexW2010274993WikidataQ59329024 ScholiaQ59329024MaRDI QIDQ2575082

Erik Winfree, David Soloveichik

Publication date: 5 December 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://authors.library.caltech.edu/22759/

zbMATH Keywords

computational complexityDNA computingcircuit complexitymolecular computingbranching programsrestriction enzymes

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Medical applications (general) (92C50) Protein sequences, DNA sequences (92D20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Exploring programmable self-assembly in non-DNA based molecular computing ⋮ Analysis and design of molecular machines ⋮ Isothermal reactivating whiplash PCR for locally programmable molecular computation ⋮ Graph-Theoretic Formalization of Hybridization in DNA Sticker Complexes ⋮ Theory of tailor automata ⋮ Graph-theoretic formalization of hybridization in DNA sticker complexes

Cites Work

• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Branching Programs and Binary Decision Diagrams

This page was built for publication: The computational power of Benenson automata