Self-Assembly for Maximum Yields Under Constraints

We present an algorithm that, given any target tree, synthesizes reversible self-assembly rules that provide a maximum yield in the sense of stochastic stability. If the reversibility constraint is relaxed then the same algorithm can be trivially modified so that it converges to a maximum yield almost surely. The proof of correctness in both cases relies on the notion of a completing rule. We examine the conservatism of this technique by considering its implications for the internal states of the system. We show by example that any algorithm that guarantees the existence of a completing rule for all target trees will, for some cases, (1) produce complete assemblies with non-unique internal states, or (2) produce internal states that cannot be recovered from the unlabeled graph.