University of Zürich and ETH Zürich, Switzerland.

tneary [at] ini [dot] phys [dot] ethz [dot] ch

I am a postdoc in the group of Matthew Cook. My area of research is Theoretical Computer Science, with my main interest lying in Models of Computation. I am particularly interested in simple Turing universal models and their computational complexity.

News: We are hosting the

T. Neary. Undecidability in Binary Tag Systems and the Post Correspondence Problem for Five Pairs of Words. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, volume 30 of LIPIcs, pages 649–661, 2015.

T. Neary. Three small universal spiking neural P systems. Theoretical Computer Science, 567:2–20, 2015.[pdf]

Matthew Cook, Urban Larsson and T. Neary. A Cellular Automaton for Blocking Queen Games. In Cellular Automata and Discrete Complex Systems, AUTOMATA 2015, volume 9099 of LNCS, pages 71–84, 2015. Springer. [arXiv]

T. Neary, D. Woods, Niall Murphy and Rainer Glaschick. Wang’s B machines are efficiently universal, as is Hasenjaeger’s small universal electromechanical toy. Journal of Complexity, 30(5):634–646, 2014.[arXiv]

T. Neary and D. Woods. The complexity of small universal Turing machines: A survey. In 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), LNCS, Špindlerův Mlýn, Czech Republic. Jan. 2012. Springer. [arXiv] (Two earlier versions of this survey appear below.)

R. Glaschick, T. Neary, D. Woods, N. Murphy. Hasenjaeger's electromechanical small universal Turing machine is time efficient. Turing in Context II. Oct 10-12, 2012. Brussles, Belgium.

T. Neary. On the computational complexity of spiking neural P systems. Natural Computing, 9(4):831–851, 2010.[pdf]

T. Neary. A universal spiking neural P system with 11 neurons. In The Eleventh International Conference on Membrane Computing, CMC11, Jena, Germany, Aug. 2010. [pdf]

T. Neary. A boundary between universality and non-universality in extended spiking neural P systems. In Language and Automata Theory and Applications, 4th International Conference, LATA 2010, volume 6031 of LNCS, pages 475–487, Trier, May. 2010. Springer.[pdf]

T. Neary and D. Woods. Small weakly universal Turing machines. 17th International Symposium on Fundamentals of Computation Theory (FCT 2009), volume 5699 of LNCS, pages 262-273, Wrocław, Poland Sept. 2009. Springer.[pdf]

T. Neary and D. Woods. Four small universal Turing machines. Fundamenta Informaticae, 91(1):123-144, 2009.[pdf]

D. Woods and T. Neary. Small semi-weakly universal Turing machines. Fundamenta Informaticae, 91(1):179-195, 2009.[pdf]

D. Woods and T. Neary. The complexity of small universal Turing machines: A survey. Theoretical Computer Science, 410(4-5):443-450, Feb. 2009. [pdf]

T. Neary. On the computational complexity of spiking neural P systems. 7th International Conference on Unconventional Computation (UC 2008), volume 5204 of LNCS, pages 189-205, Vienna, Aug. 2008. Springer.[pdf]

T. Neary. A small universal spiking neural P system. International Workshop on Computing with Biomolecules, pages 65-74, Vienna, Aug. 2008. Austrian Computer Society.[pdf]

T. Neary and D. Woods. Four small universal Turing machines. MCU 2007 - Machines, Computations, and Universality, volume 4664 of LNCS, pages 242-254, Orléans, France, Sept. 2007. Springer.[pdf]

D. Woods and T. Neary. Small semi-weakly universal Turing machines. MCU 2007 - Machines, Computations, and Universality, volume 4664 of LNCS, pages 303-315, Orléans, France, Sept. 2007. Springer.[pdf]

D. Woods and T. Neary. The complexity of small universal Turing machines. CiE 2007 - Computability in Europe, volume 4497 of LNCS, pages 791-799, Sienna, Italy, June 2007. Springer.

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

D. Woods and 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, pages 439- 446, Berkeley, California, Oct. 2006. IEEE.[pdf]

T. Neary and D. Woods. P-completeness of cellular automaton Rule 110. ICALP 2006 - 33rd International Colloquium on Automata, Languages and Programming, volume 4051 of LNCS, Part I, pages 132-143, Venice, July 2006. Springer.[pdf]

T. Neary. Small polynomial time universal Turing machines. MFCSIT 2006 - Fourth Irish Conference on the Mathematical Foundations of Computer Science and Information Technology, pages 325-329, Cork, Ireland, Aug. 2006. [pdf]

D. Woods and T. Neary. Remarks on the computational complexity of small universal Turing machines. MFCSIT 2006 - In Fourth Irish Conference on the Mathematical Foundations of Computer Science and Information Technology, pages 334-338, Cork, Ireland, Aug. 2006. [pdf]

T. Neary and D. Woods. Tag Systems and the Complexity of Simple Programs. In Cellular Automata and Discrete Complex Systems, AUTOMATA 2015, volume 9099 of LNCS, pages 11–16, 2015. Springer.

D. Woods and T. Neary. Yurii Rogozhin’s Contributions to the Field of Small Universal Turing Machines. Fundamenta Informaticae, 138(1-2):251–258, 2015.

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 117–126, 2015, Springer.

T. Neary. The program-size complexity of universal Turing machines. SAS Seminar, Isaac Newton Institute for Mathematical Sciences, Cambridge, England, Apr. 2012. [slides]

T. Neary. Small universal Turing machines and computational complexity. Informatisches Kolloquium, Department of Computer Science, University of Hamburg, Germany, Dec. 2007.

T. Neary. Small polynomial time universal Turing machines. MFCSIT 2006 - Fourth Irish Conference on the Mathematical Foundations of Computer Science and Information Technology, Cork, Ireland, Aug. 2006.

T. Neary. Small universal Turing machines. PhD thesis, NUI, Maynooth, 2008. [pdf]

We hosted The Complexity of Simple Programs 2008 at the University College Cork. The proceedings were published in EPTCS, and post-proceedings published as a journal special issue of TCS.

T. Neary. Undecidability in binary tag systems and the Post correspondence problem for four pairs of words. arXiv:1312.6700 [cs.FL], 2013.

T. Neary. On the computational complexity of spiking neural P systems. arXiv:0912.0928v1 [cs.CC], 2009.

T. Neary. A boundary between universality and non-universality in spiking neural P systems. arXiv:0912.0741v1 [cs.CC], 2009.

T. Neary and D. Woods. Small weakly universal Turing machines. arXiv:0707.4489v1 [cs.CC], July 2007.

D. Woods and T. Neary. On the time complexity of 2-tag systems and small universal Turing machines. arXiv:0612.089v1 [cs.CC], Dec. 2006.

T. Neary and D. Woods. P-completeness of cellular automaton Rule 110. Technical Report 04/2006, Boole Centre for Research in Informatics, University College Cork, Ireland, 2006. [pdf]

T. Neary and D. Woods. A small fast universal Turing machine. Technical Report NUIM-CS-TR-2005-12, Department of Computer Science, National University of Ireland, Maynooth, 2005. [pdf]

T. Neary and D. Woods. Small fast universal Turing machines. Technical Report NUIM-CS-TR-2005-11, Department of Computer Science, National University of Ireland, Maynooth, 2005. [pdf]

T. Neary and D. Woods. Simulating Turing machines using switching map systems. Technical Report NUIM-CS-TR-2003-11, Department of Computer Science, National University of Ireland, Maynooth, 2003. [pdf]