Transducers with programmable input by DNA self-assembly

Nataša Jonoska, Shiping Liao, Nadrian C. Seeman

Research output: Contribution to journalArticlepeer-review


Notions of Wang tiles, finite state machines and recursive functions are tied together. We show that there is a natural way to simulate finite state machines with output (transducers) with Wang tiles and we show that recursive (computable) functions can be obtained as composition of transducers through employing Wang tiles. We also show how a programmable transducer can be self-assembled using TX DNA molecules simulating Wang tiles and a linear array of DNA PX-JX2 nanodevices.

Original languageEnglish (US)
Pages (from-to)219-240
Number of pages22
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Transducers with programmable input by DNA self-assembly'. Together they form a unique fingerprint.

Cite this