Damien Woods

Proceedings of the 29th International Conference on DNA Computing and Molecular Programming, 2023

2021

On the hardness of knowing busy beaver values BB(15) and BB(5, 4).

[BibT_eX]

[DOI]

CoRR, 2021

Small Tile Sets That Compute While Solving Mazes.

[BibT_eX]

[DOI]

Matthew Cook

Proceedings of the 27th International Conference on DNA Computing and Molecular Programming, 2021

2020

Limitations on counting in Boolean circuits and self-assembly.

[BibT_eX]

[DOI]

CoRR, 2020

The program-size complexity of self-assembled paths.

[BibT_eX]

[DOI]

Pierre-Étienne Meunier

Damien Regnault

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The Collatz Process Embeds a Base Conversion Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Reachability Problems - 14th International Conference, 2020

Turning Machines.

[BibT_eX]

[DOI]

Irina Kostitsyna

Cai Wood

Proceedings of the 26th International Conference on DNA Computing and Molecular Programming, 2020

2019

Diverse and robust molecular algorithms using reprogrammable DNA self-assembly.

[BibT_eX]

[DOI]

Nat., 2019

2018

Preface.

[BibT_eX]

[DOI]

Yannick Rondelez

Nat. Comput., 2018

2017

The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation.

[BibT_eX]

[DOI]

Pierre-Étienne Meunier

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Thermodynamic Binding Networks.

[BibT_eX]

[DOI]

Proceedings of the DNA Computing and Molecular Programming - 23rd International Conference, 2017

2016

Intrinsic Universality in Self-Assembly.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Active Self-Assembly and Molecular Robotics with Nubots.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

The Two-Handed Tile Assembly Model is not Intrinsically Universal.

[BibT_eX]

[DOI]

Algorithmica, 2016

2015

Parallel computation using active self-assembly.

[BibT_eX]

[DOI]

Moya Chen

Doris Xin

Nat. Comput., 2015

Yurii Rogozhin's Contributions to the Field of Small Universal Turing Machines.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2015

Tag Systems and the Complexity of Simple Programs.

[BibT_eX]

[DOI]

Proceedings of the Cellular Automata and Discrete Complex Systems, 2015

2014

Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy.

[BibT_eX]

[DOI]

J. Complex., 2014

Uniformity is Weaker than Semi-Uniformity for Some Membrane Systems.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2014

Intrinsic universality in tile self-assembly requires cooperation.

[BibT_eX]

[DOI]

Pierre-Etienne Meunier

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Fast Algorithmic Self-assembly of Simple Shapes Using Random Agitation.

[BibT_eX]

[DOI]

Proceedings of the DNA Computing and Molecular Programming - 20th International Conference, 2014

2013

AND and/or OR: Uniform Polynomial-Size Circuits

[BibT_eX]

[DOI]

Proceedings of the Proceedings Machines, Computations and Universality 2013, 2013

Intrinsic universality and the computational power of self-assembly.

[BibT_eX]

[DOI]

Proceedings of the Proceedings Machines, Computations and Universality 2013, 2013

Active self-assembly of algorithmic shapes and patterns in polylogarithmic time.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece

[BibT_eX]

[DOI]

CoRR, 2012

The Tile Assembly Model is Intrinsically Universal.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Preface.

[BibT_eX]

[DOI]

Anthony Karel Seda

Theor. Comput. Sci., 2011

The computational power of membrane systems under tight uniformity conditions.

[BibT_eX]

[DOI]

Nat. Comput., 2011

2010

Intrinsic Universality in Self-Assembly.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009

Optical Computing.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Complexity and Systems Science, 2009

The complexity of small universal Turing machines: A survey.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

Small Semi-Weakly Universal Turing Machines.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2009

Four Small Universal Turing Machines.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2009

Optical computing.

[BibT_eX]

[DOI]

Appl. Math. Comput., 2009

Membrane Dissolution and Division in P.

[BibT_eX]

[DOI]

Mario J. Pérez-Jiménez

Agustin Riscos-Núñez

Proceedings of the Unconventional Computation, 8th International Conference, 2009

Random Number Selection in Self-assembly.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computation, 8th International Conference, 2009

Small Weakly Universal Turing Machines.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 17th International Symposium, 2009

2008

Lower bounds on the computational power of an optical model of computation.

[BibT_eX]

[DOI]

Peter J. M. Van Der Burgt

J. Paul Gibson

Nat. Comput., 2008

Implementations of a Model of Physical Sorting.

[BibT_eX]

[DOI]

Niamh Woods

Int. J. Unconv. Comput., 2008

On acceptance conditions for membrane systems: characterisations of L and NL

[BibT_eX]

[DOI]

Proceedings of the Proceedings International Workshop on The Complexity of Simple Programs, 2008

A Characterisation of NL Using Membrane Systems without Charges and Dissolution.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computing, 7th International Conference, 2008

Parallel and Sequential Optical Computing.

[BibT_eX]

[DOI]

Proceedings of the Optical Super Computing, First International Workshop, 2008

2007

Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P.

[BibT_eX]

[DOI]

Proceedings of the Membrane Computing, 8th International Workshop, 2007

The Complexity of Small Universal Turing Machines.

[BibT_eX]

[DOI]

Proceedings of the Computation and Logic in the Real World, 2007

2006

Small fast universal Turing machines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Optical Computing and Computational Complexity.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computation, 5th International Conference, 2006

P-completeness of Cellular Automaton Rule 110.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

On the time complexity of 2-tag systems and small universal Turing machines.

[BibT_eX]

[DOI]

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

An optical model of computation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Upper Bounds on the Computational Power of an Optical Model of Computation.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Complexity of Continuous Space Machine Operations.

[BibT_eX]

[DOI]

J. Paul Gibson

Proceedings of the New Computational Paradigms, 2005

2001

On the Computational Power of a Continuous-Space Optical Model of Computation.

[BibT_eX]

[DOI]