Turlough Neary

Institute for Neuroinformatics,
University of Zürich and ETH Zürich,
Switzerland.
tneary [at] ini [dot] phys [dot] ethz [dot] ch

I am a research scientist in the group of Matthew Cook. My area of research is theoretical computer science, with my main interest lying in models of computation and computational complexity. I am particularly interested in simple Turing universal models and their computational complexity.

Publications

M. Cook and T. Neary. Average-Case Completeness in Tag Systems. In 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, volume 126 of LIPIcs, pages 20:1–20:17, 2019

T. Neary and M. Cook. Generalized Tag Systems. In Reachability Problems (RP 2018), volume 11123 of LNCS, pages 103–116, 2018. Springer.

T. Neary. 2-State 2-Symbol Turing Machines with Periodic Support Produce Regular Sets. In Descriptional Complexity of Formal Systems, DCFS 2017, volume 10316 of LNCS, pages 274–286, 2017. Springer.

M. Cook, U. Larsson and T. Neary. A cellular automaton for blocking queen games. Natural Computing, 16(3):397–410, 2017.

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]

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, 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]

Invited presentations

Average-case NP-completeness in 2-tag systems. Workshop on Self-assembly, Geometry and Computation, Fontainebleau, France, June 2018.

The Complexity of Simple Programs. Special Seminar, Department of Industrial Engineering and Management, Technion, Haifa, Israel, February 2017.

Tag Systems and the Complexity of Simple Programs. 21st International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2015.

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

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

Conferences

Co-chair and organizer: AUTOMATA 2016, MCU 2013, The Complexity of Simple Programs 2008.

Program committee: MCU 2015, UCNC 2016, UCNC 2017, MCU 2018, UCNC 2018, AUTOMATA 2019, UCNC 2019, CiE 2020.

Steering committee: AUTOMATA 2017, AUTOMATA 2019,

Proceedings edited

AUTOMATA 2016 published in LNCS, and post-proceedings published in Natural Computing.

MCU 2013 published in EPTCS.

Complexity of Simple Programs 2008 published in EPTCS, and post-proceedings published in TCS.

PhD thesis

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

Technical reports

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]