Assembly theory: formalizing assembly spaces, discovering patterns and bounds

Abstract Assembly theory defines structural complexity as the minimum number of steps required to construct an object in an assembly space. We formalize the assembly space as an acyclic digraph of strings. Key results include analytical bounds on the minimum and maximum assembly indices (ASIs) as functions of the string length and alphabet size, as well as relations between the ASI, assembly depth, depth index, Shannon entropy and expected waiting times for strings drawn from uniform distributions. We identify patterns in minimum- and maximum-ASI strings and provide construction methods for the latter. While computing ASI is NP-complete, we develop efficient implementations that enable ASI computation of long strings. We establish a counterintuitive, inverse relationship between a string ASI and its expected waiting time. Ordered decimal representations of low ASI bitstrings of even length N naturally cluster on diagonals and oblique lines of the squares with sides equal to 2N/2. Comparison with dictionary-based (LZW) and grammar-based (Re-Pair) compression schemes shows that ASI provides superior compression by exploiting global combinatorial patterns. These findings advance the use of complexity measures in computational biology, graph theory and data compression.