Damien Woods
Caltech

I've moved to Caltech, you should be redirected to my new webpage. I previously worked in the Research Group on Natural Computing at the University of Seville and the Cork Complex Systems Lab (CCSL) in University college Cork. Before that I was at the Boole Centre For Research in Informatics and the School of Mathematics. I did my PhD at the Department of Computer Science at NUI Maynooth. Some conferences that I'm involved with: TCS 2010, MCU 2010, UC 2010, OSC 2010, DCM 2009, OSC '09, UC '08, OSC '08, MCU '07, UC '07, MFCSIT '06, UC '06 (workshop). I was one of the co-chairs of Complexity of Simple Programs 2008, the proceedings of which are here.

---

Publications
Small universal Turing machines
Optical computing
Biological & membrane computing
Tile self-assembly


Small universal Turing machines & other simple universal systems

T. Neary, D. Woods. Small weakly universal Turing machines.
Conference version: FCT 2009 - 17th International Symposium on Fundamentals of Computation Theory, Wrocław, Poland. Springer LNCS, vol. 5699: 262-273. M. Kutylowski, M. Gebala, W. Charatonik (editors). [pdf]
arXiv version: (July 2007) arXiv:0707.4489v1 [cs.CC]

D. Woods, T. Neary. "Small semi-weakly universal Turing machines".
Journal version: Fundamenta Informaticae. 91:161-177 (2009). (Special issue for MCU 2007) [pdf]
Conference version: Machines, Computations, and Universality (MCU) 2007, Orléans, France. Springer LNCS, vol. 4664:303-315. J. Durand-Lose, M. Margenstern (editors). [pdf]

T. Neary, D. Woods. "Four small universal Turing machines".
Journal version: Fundamenta Informaticae. 91:105-126 (2009). (Special issue for MCU 2007) [pdf]
Conference version: Machines, Computations, and Universality (MCU) 2007, Orléans, France. Springer LNCS, vol. 4664:242-254 J. Durand-Lose, M. Margenstern (editors). [pdf]

D. Woods, T. Neary, "The complexity of small universal Turing machines". (Invited survey.)
Conference version: Computation and Logic in the Real World - Third Conference of Computability in Europe, CiE 2007, Siena, Italy, June 2007. Springer LNCS vol. 4497. S. Barry Cooper, Benedikt Löwe, and Andrea Sorbi (editors).
Journal version: Theoretical Computer Science 410(4-5), Feburary 2009, pp 443-450. [pdf] (Draft from 18/10/2007)

D. Woods, T. Neary, "On the time complexity of 2-tag systems and small universal Turing machines", FOCS - 2006, 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2006, Berkeley, California. pp 439-446. [pdf]

T. Neary, D. Woods, "P-completeness of cellular automaton Rule 110", ICALP 2006 - International Colloquium on Automata Languages and Programming, Venice, Italy. Springer LNCS vol. 4051, part 1, pp 132-143. [pdf] [.ps]

D. Woods, T. Neary. "Remarks on the computational complexity of small universal Turing machines". MFCSIT 2006. Cork, Ireland. pp 334-338. [pdf]

T. Neary, D. Woods, "Small fast universal Turing machines," Theoretical Computer Science, 362(1-3): 171-195, 11 October 2006. [pdf]


Optical computing

D. Woods, T. J. Naughton, "Optical Computing"
Journal version: Applied Mathematics and Computation, 215(4): 1417-1430, October 2009. (Special issue on Physics and Computation) [pdf]
Conference version: Workshop on Physics and Computation, Vienna, August, 2008. Pre-proceedings 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 70-86. [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 27-40 [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 777-788. [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): 95-108. March 2008. Springer. [pdf]
Conference version: UC'05 - Fourth International Conference on Unconventional Computation, Sevilla, October 2005. Springer LNCS vol 3699, pp 237-250. [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 540-551. [pdf] [.ps]

D. Woods, T. J. Naughton, "An optical model of computation," Theoretical Computer Science, 334(1-3): 227-258, April 2005. [pdf]

T. J. Naughton, D. Woods, "On the computational power of a continuous-space 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. 288-299. [pdf] [.ps]


Biological & membrane computing

D. Woods, N. Murphy, M.J. Pérez-Jiménez, A. Riscos-Núñez. Membrane dissolution and division in P. UC'09 - Eighth International Conference on Unconventional Computation, Ponta Delgada (Azores), Portugal. Springer LNCS, vol 5715 , pp 268-282 [pdf]

N. Murphy, D. Woods. "The Computational Complexity of Uniformity and Semi-uniformity in Membrane Systems" (Unrefereed Technical Report in Seventh Brainstorming Week on Membrane Computing 2009). [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 556-560. [pdf] (A short survey highlighting some of our work.)

N. Murphy, D. Woods. "On acceptance conditions for membrane systems: characterisations of L and NL", The Complexity of Simple Programs, Cork, Ireland, 6-7 december, 2008. Cork University Press, pp 225-242. [pdf]

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 164-176 [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 367-384. [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".
Conference version: Pre-proceedings of the workshop From Utopian to Genuine Unconventional Computers (part of UC'06), York, UK. Luniver Press, pp 79-99. [pdf]
Journal version: International Journal of Unconventional Computing, 4(1), pp 3-12, 2008.

N. Murphy, D. Woods, T. J. Naughton. "Bio-Computation using Holliday junctions". MFCSIT 2006. Cork, Ireland. pp 317-320. [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 1-7. [.ps]


Tile self-assembly

D.S. Doty, J.H. Lutz, M.J. Patitz, S.M. Summers, D.Woods. Intrinsic Universality in Self-Assembly. STACS 2010 - Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, (Nancy, France, March 4-6, 2010). [pdf]

D.S. Doty, J.H. Lutz, M.J. Patitz, S.M. Summers, D.Woods. Random number selection in self-assembly. UC'09 - Eighth International Conference on Unconventional Computation, Ponta Delgada (Azores), Portugal. To appear. [pdf]

PhD thesis

D. Woods, "Computational Complexity of an optical model of computation" PhD Thesis, NUI Maynooth, 2005.

Invited talks, published conference abstracts, technical reports, etc.

N. Murphy, D. Woods. "A characterisation of NL using membrane systems without charges and dissolution", Technical Report NUIM-CS-TR-2008-01, Jan 2008, Department of Computer Science, National University of Ireland Maynooth, Ireland. [pdf]

N. Murphy, D. Woods, T.J. Naughton, "Stable Sorting Using Special-Purpose Physical Devices", BCRI Preprint 06/2006, May 2006, Boole Centre for Research in Informatics, University College Cork, Ireland. [pdf] [.ps]

T. Neary, D. Woods, "P-completeness of cellular automaton Rule 110", BCRI Preprint 04/2006, April 2006, Boole Centre for Research in Informatics, University College Cork, Ireland. [pdf] [.ps]

T. Neary, D. Woods, "A small fast universal Turing machine" Technical Report NUIM-CS-TR-2005-12, CS Dept., NUI Maynooth, 2005. [pdf] [.ps]

T. Neary, D. Woods, "Small fast universal Turing machines" Technical Report NUIM-CS-TR-2005-11, CS Dept., NUI Maynooth, 2005. [pdf] [.ps]

N. Murphy, D. Woods, T. J. Naughton, "On the computational power of photosynthesis," Technical Report NUIM-CS-TR-2005-03, CS Dept., NUI Maynooth, July 2005. [pdf]

D. Woods, "Computational complexity of an optical model of computation," (Invited.) International workshop on computations on the continuum. Lisbon, Portugal, June 27-28, 2005.

T. Neary, D. Woods, "Simulating Turing machines using switching map systems" Technical Report NUIM-CS-TR-2003-11, NUI Maynooth, December 2003. [pdf] [.ps]

D. Woods, T. J. Naughton, J. P. Gibson, "Continuous-space model of computation," (Invited.) American Mathematical Society - Spring Western Section Meeting #987, Special Session on Beyond Classical Boundaries of Computability, M. Burgin, P. Wegner, Eds., San Francisco, California, 3-4 May 2003. Reprinted in Abstracts of Papers Presented to the American Mathematical Society, vol. 24, no. 3, p. 484, September 2003.

A. Delaney, T. J. Naughton, D.Woods, "Towards a minimal computational power operating system." In British Colloquium for Theoretical Computer Science, number 19, Leicester, UK, April 2003. [.ps] [.pdf]

D. Woods, T. J. Naughton, "Analog recurrent neural network simulation and (log₂ n) unordered search with an optically inspired model of computation" Technical Report NUIM-CS-TR-2003-04, NUI Maynooth, March 2003. [pdf] [.ps]

D. Woods, T. J. Naughton, J. Paul Gibson, "Analog recurrent neural network simulation, (log₂ n) unordered search, and bitonic sort with an optically-inspired model of computation" Technical Report NUIM-CS-TR-2001-06, NUI Maynooth, October 2001. (This report is a preliminary version of NUIM-CS-TR-2003-04 above.) [pdf]

T. J. Naughton, D. Woods, "On the computational power of a continuous-space optical model of computation" Technical Report NUIM-CS-TR-2001-01, NUI Maynooth, January 2001. [pdf]

PhD Supervision

Niall Murphy is working on membrane computing and is co-supervised by Tom Naughton.

Turlough Neary Small universal Turing machines. (PhD awarded: 2008. Examiners: Maurice Margenstern, James Power. Co-supervised by Paul Gibson)

---

URL: http://www.bcri.ucc.ie/~dw5 email: revised: Sept 06 Damien Woods Boole Centre for research in Informatics School of Mathematics University College Cork Ireland

-->