A linear bound for the size of the finite terminal assembly of a directed non-cooperative tile assembly system
Pith reviewed 2026-05-24 01:04 UTC · model grok-4.3
The pith
Non-determinism is strictly necessary to assemble efficient paths in directed non-cooperative tile assembly systems.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
In the directed non-cooperative abstract tile assembly model, any tile set that produces an efficient path must admit at least two different finite terminal assemblies; the non-determinism is therefore required. The same argument yields a linear upper bound on the size of any finite terminal assembly when the system is deterministic and shows that an n-wide square cannot be assembled with fewer than roughly 2n tile types.
What carries the argument
Directed non-cooperative aTAM, in which a tile set may produce several terminal assemblies that nevertheless all contain the same efficient path.
If this is right
- Any deterministic system in this model is limited to terminal assemblies of linear size.
- The 2n-1 tile construction for an n-by-n square cannot be improved by more than a constant factor.
- Decidability of the directed model is tied to the inability of deterministic systems to produce super-linear structures.
Where Pith is reading between the lines
- The same linear-size restriction may explain why the non-directed (undirected) variant remains undecidable.
- Extending the argument to other geometric constraints could bound the growth rate of any deterministic non-cooperative assembly.
- If the bound can be tightened to sub-linear, it would rule out even the original linear-distance efficient paths without non-determinism.
Load-bearing premise
The previously published constructions of efficient paths are correctly realized inside the directed non-cooperative model and rely on multiple terminal assemblies.
What would settle it
A deterministic directed non-cooperative tile set with n tile types whose unique terminal assembly contains a path longer than c n for some constant c.
read the original abstract
The abstract tile assembly model (aTam) is a model of DNA self-assembly. Most of the studies focus on cooperative aTAM where a form of synchronization between the tiles is possible. Simulating Turing machines is achievable in this context. Few results and constructions are known for the non-cooperative case (a variant of Wang tilings where assemblies do not need to cover the whole plane and some mismatches may occur). Introduced by P.E. Meunier, efficient paths are a non-trivial construction for non-cooperative aTAM designed with $n$ different tile types and reaching a distance linearly greater than n. Later, efficient paths were improved to be able to reach a distance of n log(n). Assembling them relies heavily on a form of ``non-determinism''. Indeed, the set of tiles may produce different finite terminal assemblies but they all contain the same efficient path, a model called directed non-cooperative aTAM. This variant of aTAM is the only one who was shown to be decidable. In this paper, we prove that this non-determinism is strictly necessary for assembling the efficient paths. This result also implies that the construction of a square of width n using 2n-1 tiles types is asymptotically optimal. Moreover, we hope that the techniques introduced here will lead to a better comprehension of the non-directed case.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proves that any finite terminal assembly in the directed non-cooperative abstract tile assembly model (aTAM) has size bounded linearly by the number of distinct tile types. It uses this bound to show that non-determinism (multiple terminal assemblies sharing an efficient path) is strictly necessary to achieve superlinear reach with n tile types, and that the known 2n-1 tile-type construction of an n×n square is asymptotically optimal.
Significance. If the result holds, it supplies a parameter-free mathematical bound separating the directed and non-directed cases of non-cooperative aTAM and explains the necessity of non-determinism in efficient-path constructions. The proof directly confirms asymptotic optimality for square assembly and may supply techniques for analyzing the non-directed model. The derivation contains no free parameters or fitted constants.
minor comments (2)
- [Introduction] The introduction would benefit from an explicit statement of the main theorem (including the precise linear constant or O-notation) immediately after the model definitions.
- Notation for the set of tile types and the directedness condition could be unified between the abstract and the technical sections to avoid minor ambiguity for readers.
Simulated Author's Rebuttal
We thank the referee for the positive review and recommendation to accept. The assessment correctly identifies the result's role in establishing a parameter-free linear bound that separates the directed and non-directed cases and confirms the asymptotic optimality of the 2n-1 tile-type square construction.
Circularity Check
No significant circularity; self-contained mathematical proof
full rationale
The paper presents a mathematical proof establishing a linear upper bound on the size of finite terminal assemblies in the directed non-cooperative aTAM and the necessity of non-determinism for efficient paths. No steps reduce by construction to fitted parameters, self-definitions, or load-bearing self-citations; the derivation relies on model definitions and prior independent constructions (e.g., Meunier et al.) treated as external inputs rather than redefined outputs. The optimality implication for square assemblies follows directly from the bound without circular renaming or ansatz smuggling. This is a standard theoretical CS proof structure with no evidence of the enumerated circularity patterns.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The definitions of efficient paths and directed non-cooperative aTAM as used in prior work.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.