41 citations · 224 across the 20 of their papers we have counts for
4 papers · 1 filter
Deterministic Non-cooperative Binding in Two-Dimensional Tile Assembly Systems Must Have Ultimately Periodic Paths
Jérôme Durand-Lose, Hendrik Jan Hoogeboom, Nataša Jonoska
We consider non-cooperative binding, so-called 'temperature 1', in deterministic or directed (called here confluent) tile self-assembly systems in two dimensions and show a necessa…
Deterministic 2-Dimensional Temperature-1 Tile Assembly Systems Cannot Compute
Jérôme Durand-Lose, Hendrik Jan Hoogeboom, Nataša Jonoska
We consider non cooperative binding in so called `temperature 1', in deterministic (here called {\it confluent}) tile self-assembly systems (1-TAS) and prove the standing conjectur…
Acyclic Constraint Logic and Games
Hendrik Jan Hoogeboom, Walter A. Kosters, Jan N. van Rijn +1
Non-deterministic Constraint Logic is a family of graph games introduced by Demaine and Hearn that facilitates the construction of complexity proofs. It is convenient for the analy…
Tetris is Hard, Even to Approximate
Erik D. Demaine, Susan Hohenberger, David Liben-Nowell
In the popular computer game of Tetris, the player is given a sequence of tetromino pieces and must pack them into a rectangular gameboard initially occupied by a given configurati…