Assembly theory: formalizing assembly spaces, discovering patterns and bounds
Royal Society Open Science · 27.05.2026 · 13 (5)
DOI: 10.1098/rsos.260082 ↗Kurz gefasst
Fachartikel in der Zeitschrift Royal Society Open Science, online erschienen am 27.05.2026. Verfasst von Wawrzyniec Bieniawski und 4 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 56 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Bieniawski, W., Masierak, P., Tomski, A., Łukaszyk, S., & Tworz, S. (2026). Assembly theory: formalizing assembly spaces, discovering patterns and bounds. Royal Society Open Science, 13(5). https://doi.org/10.1098/rsos.260082
Vancouver
Bieniawski W, Masierak P, Tomski A, Łukaszyk S, Tworz S. Assembly theory: formalizing assembly spaces, discovering patterns and bounds. Royal Society Open Science. 2026;13(5). doi:10.1098/rsos.260082
BibTeX
@article{Bieniawski2026,
author = {Bieniawski, Wawrzyniec and Masierak, Piotr and Tomski, Andrzej and Łukaszyk, Szymon and Tworz, Szymon},
title = {Assembly theory: formalizing assembly spaces, discovering patterns and bounds},
journal = {Royal Society Open Science},
year = {2026},
volume = {13},
number = {5},
doi = {10.1098/rsos.260082}
}
EUVIMED