

Publications by topic [α] = Alphabetical author order Experimental: Molecular computers, DNA nanostructures Damien Woods*, David Doty*, Cameron Myhrvold, Joy Hui, Felix Zhou, Peng Yin, Erik Winfree (*Joint first authors) Diverse and robust molecular algorithms using reprogrammable DNA selfassembly Nature 567:366372. 2019 [pdf], [bib] Supplementary Info A (theory, design, results), Suppl Info B (DNA sequences), Suppl Info C (Sample data); Sequence design code, AFM images and analysis code, Raw data (Bruker file format). Presentation: Keynote at DNA26 Media: The Irish Times, Chemistry World, PhysicsWorld, Wired, IEEE Spectrum, Silicon Republic, Europa Press (in Spanish), Nature Asia, The California Aggie. Live interviews: Futureproof on Newstalk radio, short video interview, The Wider View on Northern Sound. Press releases: Maynooth University, Inria (in French), Caltech, UC Davis. An art exhibition with some quirky visitors. Erik's blurbification. Anupama J. Thubagere, Wei Li, Robert F. Johnson,Zibo Chen, Shayan Doroudi, Yae Lim Lee, Gregory Izatt, Sarah Wittman, Niranjan Srinivas, Damien Woods, Erik Winfree, Lulu Qian A cargosorting DNA robot Science 357(6356). 2017 [paper] [Supplementary material] Theory: Algorithms for nucleic acid (DNA/RNA) prediction Ahmed Shalaby, Chris Thachuk, Damien Woods Minimum free energy, partition function and kinetics simulation algorithms for a multistranded scaffolded DNA computer DNA29: The 29th International Conference on DNA Computing and Molecular Programming Schloss Dagstuhl—LeibnizZentrum für Informatik LIPIcs:1:11:22, 2023, [Open Access full paper], [bib] Theory: Selfassembly, intrinsic universality [α] Matthew Cook, Tristan Stérin, Damien Woods Small tile sets that compute while solving mazes. DNA27: Proceedings of the 27th International Conference on DNA Computing and Molecular Programming. LIPIcs, Schloss DagstuhlLeibnizZentrum für Informatik. 205:8:18:20, 2021. [LIPIcs version], Full [arxiv] version. [α] PierreÉtienne Meunier, Damien Regnault, Damien Woods The programsize complexity of selfassembled paths. STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. June 2020, pp 727737. Published ACM version. Full [arxiv] version, [pdf], [bib], YouTube video! [α] David Doty, Trent Rogers, David Soloveichik, Chris Thachuk, Damien Woods Thermodynamic Binding Networks. DNA23: The 23rd International Conference on DNA Computing and Molecular Programming. Springer LNCS 10467:249266, 2017. [pdf] [arxiv] [α] PierreÉtienne Meunier, Damien Woods The noncooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation. STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. pp. 328341. Published ACM version. Full [arxiv] version, [pdf], [bib]. Damien Woods Intrinsic universality and the computational power of selfassembly. (Survey article) Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences. 373(2046):20140214. Author copy: [pdf] Conference version: MCU: Machines, Computations and Universality 2013, Zürich, Switzerland, Sept. 2013. Edited by Turlough Neary and Matthew Cook. Electronic Proceedings in Theoretical Computer Science 128, pp. 1622. (Invited survey) [EPTCS] [α] Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods One tile to rule them all: simulating any Turing machine, tile assembly system, or tiling system with a single puzzle piece. ICALP: 41st International Colloquium on Automata, Languages and Programming. July, 2014. Springer LNCS 8572, pages 368379. Copenhagen, Denmark. [arxiv] [α] PierreÉtienne Meunier, Matthew J. Patitz, Scott M. Summers, Guillaume Theyssier, Andrew Winslow, Damien Woods Intrinsic universality in tile selfassembly requires cooperation. SODA: Proceedings of the 25th SIAM Symposium on Discrete Algorithms, 2014, 752771. [pdf] [arxiv] [Short version] [α] Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods The twohanded tile assembly model is not intrinsically universal. Algorithmica. 2016, 74(2):812850. ICALP: 40th International Colloquium on Automata, Languages and Programming. Proceedings, part 1. July, 2013. Springer LNCS 7965, pages 400412. Riga, Latvia [pdf] [arxiv] [α] D.S. Doty, J.H. Lutz, M.J. Patitz, R.T. Schweller, S.M. Summers, D.Woods. The tile assembly model is intrinsically universal FOCS 2012: The 53rd Annual Symposium on Foundations of Computer Science. Oct 2023. IEEE. pp 302310. [arxiv] [pdf] [Erik's blurbification] [α] D.S. Doty, J.H. Lutz, M.J. Patitz, S.M. Summers, D.Woods. Intrinsic Universality in SelfAssembly STACS 2010: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, (Nancy, France, March 46, 2010). [pdf] [arxiv] [α] D.S. Doty, J.H. Lutz, M.J. Patitz, S.M. Summers, D.Woods Random number selection in selfassembly. UC 2009: Eighth International Conference on Unconventional Computation, Ponta Delgada (Azores), Portugal. Springer LNCS, vol 5715 , pp 143157. [pdf] Theory: molecular robots, active selfassembly Irina Kostitsyna, Cai Wood, Damien Woods Turning machines: a simple algorithmic model for molecular robotics. Natural Computing. Open Access. 2022. doi: 10.1007/s11047022098808, [bib], [Full arXiv version], [blog post and videos]. Earlier conference version: DNA26: The 26th International Conference on DNA Computing and Molecular Programming. 2020. LIPIcs vol 174, pages 11:111:21. [α] HoLin Chen, David Doty, Dhiraj Holden, Chris Thachuk, Damien Woods, ChunTao Yang. Fast algorithmic selfassembly of simple shapes using random agitation. DNA20: The 20th International Conference on DNA Computing and Molecular Programming. Sept. 2014. Springer LNCS 8727, pages 2036. [LNCS] [arxiv] Moya Chen, Doris Xin, Damien Woods. Parallel computation using active selfassembly. Natural Computing, 14(2):225250. 2015. Journal [arxiv] Conference version: DNA19: The 19th International Conference on DNA Computing and Molecular Programming. Sept. 2013. Springer LNCS 8141:1630. [short version] (Moya won the Best Student Paper award!) Damien Woods, HoLin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, Peng Yin. Active SelfAssembly of Algorithmic Shapes and Patterns in Polylogarithmic Time. ITCS 2013: Innovations in Theoretical Computer Science. Berkeley, California, pages 353354, Jan. 2013. Full paper: [pdf], [arxiv], [blurbification], [Slides]. ACM 2page extended abstract: [ACM]. Theory: Small universal Turing machines, Rule 110, simple universal systems, Collatz Tristan Stérin, Damien Woods On the hardness of knowing busy beaver values BB(15) and BB(5,4) Preprint. [arXiv:2107.12475] [cs.LO] [simulator] Tristan Stérin, Damien Woods The Collatz process embeds a base conversion algorithm RP2020: 14th International Conference on Reachability Problems. 2020. Springer LNCS 12448:131147 [arXiv:2007.06979] [cs.DM] D. Woods and T. Neary. Yurii Rogozhin's Contributions to the Field of Small Universal Turing Machines. Fundamenta Informaticae, 138(12):251258, 2015. [pdf] T. Neary and D. Woods. Maurice Margenstern's Contributions to the Field of Small Universal Turing Machines. In Andrew Adamatzky (ed.) Automata, Universality, Computation  Tribute to Maurice Margenstern, pages 117126, 2015, Springer. T. Neary, D. Woods, N. Murphy, R. Glaschick. Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy. Journal of Complexity. Oct, 2014. 30(5):634646 [arXiv:1304.0053] [cs.CC] Conference version: R. Glaschick, T. Neary, D. Woods, N. Murphy: Hasenjaeger's electromechanical small universal Turing machine is time efficient. Turing in Context II. Oct 1012, 2012. Abstract, page 22. Brussels, Belgium. T. Neary, D. Woods. The complexity of small universal Turing machines: A survey. SOFSEM 2012: 38th Intl. Conf. on Current Trends in Theory and Practice of Computer Science. Špindlerův Mlýn, Czech Republic. January, 2012. Springer LNCS 7147:385405. [arxiv] Older version: D. Woods, T. Neary, "The complexity of small universal Turing machines: A survey". Theoretical Computer Science 410(45):443450, 2009. (Invited) [pdf] Even older version: D. Woods, T. Neary, "The complexity of small universal Turing machines", CiE 2007: Conference of Computability in Europe, Siena, Italy, June 2007. Springer LNCS vol. 4497. S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi (editors). T. Neary, D. Woods. Small weakly universal Turing machines. FCT 2009  17th International Symposium on Fundamentals of Computation Theory, Wrocław, Poland. Springer LNCS, vol. 5699: 262273. M. Kutylowski, M. Gebala, W. Charatonik (editors). [pdf], arXiv version: [arxiv] [cs.CC] July 2007 D. Woods, T. Neary. Small semiweakly universal Turing machines. Journal version: Fundamenta Informaticae. 91:179195 (2009). (Special issue for MCU.) [pdf] (Note that the pdf has incorrect page numbers) Conference version: Machines, Computations, and Universality (MCU) 2007, Orléans, France. Springer LNCS, vol. 4664:303315. J. DurandLose, M. Margenstern (editors). [pdf] T. Neary, D. Woods. Four small universal Turing machines. Journal version: Fundamenta Informaticae. 91:123144 (2009). (Special issue for MCU.) [pdf] (Note that the pdf has incorrect page numbers) Conference version: Machines, Computations, and Universality (MCU) 2007, Orléans, France. Springer LNCS, vol. 4664:242254 J. DurandLose, M. Margenstern (editors). [pdf] D. Woods, T. Neary. On the time complexity of 2tag systems and small universal Turing machines. FOCS  2006, 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2006, Berkeley, California. pp 439446. [pdf] T. Neary, D. Woods. Pcompleteness of cellular automaton Rule 110. ICALP 2006  International Colloquium on Automata Languages and Programming, Venice, Italy. Springer LNCS vol. 4051, part 1, pp 132143. [pdf] [ps] D. Woods, T. Neary. Remarks on the computational complexity of small universal Turing machines. MFCSIT 2006. Cork, Ireland. pp 334338. [pdf] T. Neary, D. Woods. Small fast universal Turing machines Theoretical Computer Science, 362(13): 171195, 11 October 2006. [pdf] Theory: Optical computing D. Woods, T. J. Naughton Optical computing: Photonic neural networks. Nature Physics, News and Views, 8(4):257259, April 2012. [pdf] D. Woods, T. J. Naughton Optical Computing. Journal version: Applied Mathematics and Computation, 215(4): 14171430, October 2009. (Special issue on Physics and Computation) [pdf] Conference version: Workshop on Physics and Computation, Vienna, August, 2008. Preproceedings published as CDMTCS Research Report 327 (July 2008). Invited. [pdf] D. Woods, T. J. Naughton Parallel and sequential optical computing. International Workshop on Optical Supercomputing. Vienna, August 2008. Springer LNCS vol 5172, pp 7086. [pdf] T. J. Naughton, D. Woods Optical Computing. In R. Meyer ed., Encyclopedia of Complexity and System Science, Springer. 2009 (Invited survey chapter). D. Woods Optical computing and computational complexity. UC'06  Fifth International Conference on Unconventional Computation, York, UK 2006, Springer LNCS, vol 4135 , pp 2740 [pdf] [ps], (invited.) D. Woods Upper bounds on the computational power of an optical model of computation. ISAAC 2005  The 16th Annual International Symposium on Algorithms and Computation, Sanya, Hainan, China, December 2005. Springer LNCS, vol 3827, pp 777788. [pdf] [ps] D. Woods, J. P. Gibson Lower bounds on the computational power of an optical model of computation. Journal version: Natural Computing, 7(1): 95108. March 2008. Springer. [pdf] Conference version: UC'05  Fourth International Conference on Unconventional Computation, Sevilla, October 2005. Springer LNCS vol 3699, pp 237250. [pdf] [ps] D. Woods, J. P. Gibson Complexity of continuous space machine operations. CiE'05  Computability in Europe 2005: New Computational Paradigms, Amsterdam, June 2005, S. B. Cooper, B. Löwe, and L. Torenvliet, Eds. Springer LNCS vol. 3526, pp 540551. [pdf] [ps] D. Woods, T. J. Naughton An optical model of computation. Theoretical Computer Science, 334(13): 227258, April 2005. [pdf] T. J. Naughton, D. Woods On the computational power of a continuousspace optical model of computation. MCU 2001  Third International Conference on Machines, Computations and Universality 2001, Maurice Margenstern and Yurii Rogozhin, Eds., Chisinau, Moldova, May 2001. Springer LNCS vol. 2055, pp. 288299. [pdf] [ps] Theory: Computational complexity, membranes, Boolean circuits N. Murphy, D. Woods Uniformity is weaker than semiuniformity for some membrane systems. Fundamenta Informaticae. 134(12): 129152. 2014. [arXiv] N. Murphy, D. Woods AND and/or OR: Uniform PolynomialSize Circuits. MCU 2013: Machines, Computations and Universality. Turlough Neary and Matthew Cook (Eds). Zürich, Switzerland, Electronic Proceedings in Theoretical Computer Science 128:150166. [EPTCS]. Older version [arxiv] [cs.CC] Dec 2012 N. Murphy, D. Woods Uniformity conditions in natural computing. DNA 16  The 16th International Conference on DNA Computing and Molecular Programming. Hong Kong, China, June 1417, Preproceedings, 2010, pp. 109120. (Early conference version of the above two papers.) Niall got the Best Student Paper award!. D. Woods, N. Murphy, M.J. PérezJiménez, A. RiscosNúñez Membrane dissolution and division in P. UC'09: Eighth International Conference on Unconventional Computation, Ponta Delgada (Azores), Portugal. Springer LNCS, vol 5715 , pp 268282 [pdf] N. Murphy, D. Woods Uniformity: Uncovering the Frontier of Parallelism. Proceedings of the 10th Workshop on Membrane Computing, Curtea de Argeş, Romania, 2009. Pages 556560. [pdf] (A short survey highlighting some of our work.) M.J. PérezJiménez, A. RiscosNúñez, A. RomeroJiménez, D. Woods Complexity: Membrane division, membrane creation. The Oxford Handbook of Membrane Computing, Oxford University Press. Gh. Paun, G. Rozenberg, A. Salomaa (eds). 2009, Chapter 12, pp. 302336. N. Murphy, D. Woods On acceptance conditions for membrane systems: characterisations of L and NL. The Complexity of Simple Programs, Cork, Ireland, 67 december, 2008. Cork University Press, pp 225242. [pdf] [arxiv] [cs.CC] Jun 2009. N. Murphy, D. Woods The computational power of membrane systems under tight uniformity conditions. Natural Computing, 10(1): 613631, 2011. [pdf] (Invited) Conference version: N. Murphy, D. Woods. "A characterisation of NL using membrane systems without charges and dissolution", UC'08: Seventh International Conference on Unconventional Computation, Vienna, 2008. Springer LNCS, vol 5204 , pp 164176 [pdf] N. Murphy, D. Woods Active membrane systems without charges and using only symmetric elementary division characterise P. Proceedings of the 8th Workshop on Membrane Computing, 2007, Thessaloniki, Greece. Springer LNCS vol. 4860, pp 367384. [pdf] N. Murphy, T. J. Naughton, D. Woods, B. Henley, K. McDermott, E. Duffy, P. J. M. van der Burgt, N. Woods Implementations of a model of physical sorting. International Journal of Unconventional Computing, 4(1), pp 312, 2008. [pdf] Conference version: Preproceedings of the workshop From Utopian to Genuine Unconventional Computers (part of UC'06), York, UK. Luniver Press, pp 7999. [pdf] N. Murphy, D. Woods, T. J. Naughton BioComputation using Holliday junctions. MFCSIT 2006. Cork, Ireland. pp 317320. [pdf] [ps] D. Woods, A. Trenaman Simultaneous satisfaction of hard and soft timetable constraints for a university department using evolutionary timetabling. Proceedings of Artificial Intelligence & Cognitive Science 1999, Cork, Ireland, September 1999, pp 17. [ps] PhD thesis D. Woods, "Computational Complexity of an optical model of computation" PhD Thesis, NUI Maynooth, 2005. Some old technical reports, short conference abstracts, etc. 