English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We show the first asymptotically efficient constructions in the so-called"noncooperative planar tile assembly" model.  Algorithmic self-assembly is the study of the local, distributed,asynchronous algorithms ran by molecules to self-organise, in particular duringcrystal growth. The general cooperative model, also called "temperature 2",uses synchronisation to simulate Turing machines, build shapes using thesmallest possible amount of tile types, and other algorithmic tasks. However,in the non-cooperative ("temperature 1") model, the growth process is entirelyasynchronous, and mostly relies on geometry. Even though the model looks like ageneralisation of finite automata to two dimensions, its 3D generalisation iscapable of performing arbitrary (Turing) computation, and of universalsimulations, whereby a single 3D non-cooperative tileset can simulate thedynamics of all possible 3D non-cooperative systems, up to a constant scalingfactor.  However, it was shown that the original 2D non-cooperative model is notcapable of universal simulations, and the question of its computational poweris still widely open. Here, we show an unexpected result, namely that thismodel can reliably grow assemblies of size Omega(n log n) with only n tiletypes, which is the first asymptotically efficient positive construction.

Non-cooperatively assembling large structures: a 2D pumping lemma cannot be as powerful as its 1D counterpart