Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Assembly in Directed Hypergraphs

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Assembly theory is a shortest-path problem on hypergraphs

desk verdict Solid formal translation of assembly into B-hyperpath problems, with a real proof gap in the multi-product generalization and a striking but not fully reproducible cyclization critique. read the letter →

arxiv 2505.22826 v1 pith:RFWLO7BT submitted 2025-05-28 cs.DM

Christoph Flamm , Daniel Merkle , Peter F. Stadler This is my paper
classification cs.DM MSC 05C6568R10
keywords assemblyindextheorydirectedhypergraphsB-hypergraphshyperpathproblemsDPOgraphrewritingretrosynthesisintegerlinearprogramming
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Assembly theory tries to quantify how hard an object is to build from simple parts by counting the minimum number of steps in a rule-based construction. This paper proves that the formal core of that theory is a known object from combinatorial optimization: a shortest B-hyperpath, i.e., a minimal set of hyperedges, each with one output and several inputs, that produces a target from a seed set. The proof works by a bijection between assembly spaces, as defined by the original authors, and acyclic subhypergraphs of B-hypergraphs whose edges have exactly two inputs; groundedness and reachability are preserved. A consequence is that the acyclicity assumption can be dropped, assembly generalizes to arbitrary reaction networks including multi-product reactions, and the assembly index becomes one cost function among many that can be minimized by standard hyperpath algorithms and integer linear programming. The paper also argues that ignoring cyclization steps, as the original assembly index does, makes a single ring-closure step sometimes raise, sometimes lower, and sometimes leave the complexity measure unchanged.

What carries the argument

The carrying object is the B-hypergraph: a directed hypergraph in which every hyperedge has exactly one head vertex and an arbitrary multiset of tail vertices. The paper starts with assembly spaces, edge-labeled multigraphs with the symmetry condition that if x and y combine to z, then y and x also combine to z, and converts each such step into a hyperedge $(\{x,y\},\{z\})$, with a doubled copy $(\{x,x\},\{z\})$ when $x=y$. The second ingredient is the B-hyperpath, a minimal subhypergraph linearly ordered so that every tail vertex is produced by an earlier hyperedge; the paper identifies assembly pathways with these hyperpaths. Finally, for general reaction networks the paper uses a partial order on hyperedges ('a step can fire only after all its inputs have been produced') and an inverse double-pushout graph-rewriting rule, so that assembly of a target can be computed by disassembling it and solved as an integer linear program.

What would settle it

Build an artificial chemistry with objects A and B in which the rule is order-sensitive: A+B produces C, but B+A produces D. The assembly-space symmetry condition demands edges for both orders, so the translated hypergraph would need two different single heads for the same tail {A,B}, violating the B-hypergraph property; in that system minimum assembly pathways and minimum B-hyperpaths would then diverge, refuting the claimed equivalence for order-dependent assembly.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is Proposition 2.1: there is a one-to-one correspondence, preserving groundedness and reachability, between assembly spaces in the sense of the edge-labeled multigraph definition and acyclic subhypergraphs of B-hypergraphs with $|E^{-}|=2$ for every hyperedge. Each assembly step 'x and y merge to form z' becomes a hyperedge with tail $\{x,y\}$ and head $\{z\}$; the symmetry condition imposed on assembly spaces translates exactly into the unordered multiset tail. Because every minimal assembly pathway is then a minimal B-hyperpath from a seed set to the target, the paper can drop the requirement that the underlying space be acyclic and can define assembly in arbitrary directed hypergraphs, where a reaction may have several products. In that general setting the assembly index is the minimum number of hyperedges (or, equivalently for B-hypergraphs, the number of non-minimal vertices) in an assembly pathway satisfying a reachability partial order. The paper further shows that the same hypergraph carries the grammar-compression interpretation of assembly and that the inverse of a graph-rewriting rule turns assembly into a disassembly search, exactly the shape of retrosynthetic analysis.

Load-bearing premise

The translation assumes assembly is an unordered merging of two objects that always yields the same product: if combining x and y can give different products depending on context or order, a hyperedge with tail {x,y} and a single head cannot faithfully represent the process.

Editorial extensions

If this is right

  • The assembly index of a molecule can be computed as the length of a shortest B-hyperpath in a rule-derived hypergraph, making available dynamic-programming and integer-linear-programming algorithms from the hyperpath literature.
  • The acyclicity assumption on assembly spaces can be dropped: cyclic reaction networks, including catalytic cycles, are expressible as assembly systems once one passes to minimal B-hyperpaths or to the partial-order definition.
  • Assembly theory becomes a special case of retrosynthetic analysis: inverting graph-rewriting rules turns construction of a target into a search over disassembly steps, the same procedure used in synthesis planning.
  • Because the assembly index ignores cyclizations, it produces chemically questionable witnesses; cost measures such as total weight of starting materials, which charge for cyclizations, yield different and more convergent plans in the paper's cubane and pyrrolidine-dimer examples.
  • The grammar-compression reading persists in the hypergraph setting: every minimal assembly pathway yields an acyclic context-free grammar generating the target, so assembly sits in the same family as straight-line programs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: if assembly index is a shortest-hyperpath measure, then the open question the paper flags—whether shortest B-hyperpaths remain NP-hard when every tail has size 2—directly controls whether the assembly index for rule-based chemistries can be computed efficiently in practice.
  • Editorial extension: the cyclization critique suggests a simple test: on a dataset of isomeric cyclic and acyclic molecules, compare assembly-index rankings with a cyclization-charging cost; if rankings diverge substantially, claims that assembly index tracks synthetic difficulty are about a different quantity.
  • Editorial extension: because B-hyperpaths can be encoded as integer flows, the paper's integer-linear-programming formulation should extend to enumerating all optimal assembly witnesses, not just one, which would make it possible to test how often the chemically questionable plans are the only optimal ones.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. This manuscript formalizes assembly theory in terms of directed hypergraphs. The authors show that the assembly spaces of Marshall et al. correspond to acyclic B-hypergraphs with binary tails (Prop. 2.1), that assembly pathways in B-hypergraphs coincide with minimal B-hyperpaths so that the acyclicity assumption on the underlying space can be dropped, and they propose a definition of assembly pathway on general directed hypergraphs (Def. 2.5) using a partial order on hyperedges. They connect the construction to grammar compression, DPO graph rewriting, and retrosynthetic analysis, present an ILP formulation for computing optimal assembly-index witnesses, and report case studies on cubane and a pyrrolidine dimer to illustrate that ignoring cyclization costs produces chemically questionable synthesis plans.

Significance. The reformulation is potentially valuable: it connects assembly theory to the mature literature on directed hyperpath problems and to computational synthesis planning, and it suggests concrete generalizations to multi-product chemical reactions. The paper is commendably explicit about a counterintuitive property of the assembly index with respect to cyclizations, and it introduces no fitted parameters; the translation in Prop. 2.1 is a clean and convincing reformulation. If the generalization lemma is repaired, the framework could become a useful common language for assembly theory, retrosynthetic planning, and graph-rewriting models of chemistry. The computational contribution, however, is currently undermined by an incorrect ILP objective, and the main generalization claim rests on an unproven lemma, so the paper needs substantial revision before the advertised claims are supported.

major comments (3)
  1. [Section 2.4, Lemma 2.3] The proof of Lemma 2.3 is incomplete. In the if-direction, the induced relation E≺F, defined by the existence of z∈E^+ and y∈F^+ with (E^-,{z}) ≺^B (F^-,{y}), is asserted to be a partial order on E(P), but no argument is given for transitivity or antisymmetry. The relation can fail transitivity when a hyperedge E produces a vertex y that is also a product of F, while F precedes G via a different product y'; the proof does not rule out such configurations. The proof also does not show that the subset of original edges remaining after the deletion step satisfies condition (iii) of Def. 2.5. In the only-if direction, the deletion of B-hyperedges with heads in S or with duplicated heads is not shown to preserve the target x, groundedness, or the tail-reachability condition. Because Def. 2.5, Prop. 2.2, and the claimed generalization to arbitrary chemical reaction systems rest on this lemma, this is a load-bearing gap that must be closed; for example, one could order original hyperedges according to a linear extension of the B-edge partial order rather than the unverified induced relation.
  2. [Section 2.5, Prop. 2.2] The proof of Proposition 2.2 is under-specified. The claim that each hyperedge E of a minimal pathway has a vertex y_E ∈ E^+ that is 'not contained in S or a hyperedge E' ≺ E^+' is ambiguous, and the subsequent assertion that the corresponding B-hyperedge (E^-,{y_E}) must be contained in a minimal pathway obtained by hyperedge-removal from P^B is not justified. Since the proposition is used to argue that counting original hyperedges versus B-hyperedges yields genuinely different assembly indices in general, a rigorous proof or a precise counterexample is needed.
  3. [Appendix 5.2, ILP objective] The ILP cost function min Σ_e (1000 w_e − 1) x_e does not do what the text claims. For cyclization edges (w_e=0) the term is −1, so the objective rewards adding more cyclizations; this is the opposite of the stated goal that 'the −1 favors smaller sets of hyperedges'. The intended lexicographic objective is, for example, M·Σ_e(w_e x_e) + Σ_e x_e with M > |E|, or equivalently a per-edge coefficient of M w_e + 1. As written, the ILP will not select the intended minimum-affixation, minimum-edge witness, so the computational results in Section 3 and Tables 1–2 need to be rechecked with a corrected objective.
minor comments (5)
  1. [Section 2.1, Prop. 2.1] The phrase '1-1 correspondence' is too strong: the construction from an assembly space collapses parallel edges with the same label into a single hyperedge, and the reverse construction inserts a single edge per label. The result is better stated as a correspondence preserving reachability and groundedness up to this collapse, not a literal bijection of edge-labeled multigraphs.
  2. [Definition 2.2 and Lemma 2.1] The notation H≤[x] := (E≤x, V≤x) is inconsistent with the convention H=(V,E); the primed set V'≤x is used before it is defined; and the proof of Lemma 2.1 contains several typos, including 'SinceHbe a grounded' and 'ofH ≤[x]'. A careful rewrite of this subsection is needed for readability.
  3. [Section 2.3] There is a typo 'contruction' for 'construction', and the sentence about restricting derivations to R_y is missing a grammatical subject; please revise the description of the restricted grammar so that it reads as a complete, precise statement.
  4. [Section 2.5] The recursion c(v)=c*(v)+Σ_{u∈E(v)^-} c(u) uses the symbol E(v) without prior definition; it should be defined as the unique hyperedge with head v in the B-hyperpath, and the assumption that each non-source vertex is the head of at most one edge in a minimal pathway should be stated explicitly before the recursion is introduced.
  5. [References] Reference [53], the Nature assembly theory paper, is malformed: the entry begins 'A. theory explains, quantifies selection, and evolution. Sharma, abhishek and czégel...' instead of listing the authors and title correctly. Also, the spelling 'Vléduts' is inconsistent between the main text and reference [55].

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper is a formal translation to hypergraphs with ILP algorithms; no fitted quantity and no load-bearing self-citation is renamed as a prediction.

full rationale

The paper is a mathematical reformulation, not an empirical derivation. Proposition 2.1 explicitly translates assembly spaces of [43] into B-hypergraphs with |E−|=2, and the correspondence is built from the definitions; it is a stated equivalence, not a result that smuggles in its own conclusion. Lemma 2.2 proves the equivalence between the min-hyperedge count and the prior vertex-count definition of the assembly index by showing that in a minimal pathway every vertex is the head of at most one edge; this is an independent proof step. The ILP in the appendix directly minimizes the number of inverse affixations, i.e., it computes the quantity defined in the paper; there is no fitted parameter subsequently called a prediction. The self-citations ([3]–[9], [24]) provide prior graph-rewriting, hyperflow, and synthesis-planning techniques and a standard equivalence between augmented B-hyperpaths and grounded subhypergraphs; they are published, checkable mathematical results, and the present paper does not rely on them as the sole justification of a claimed prediction. The skeptical concern about Lemma 2.3 is a proof gap: the relation induced on original hyperedges is not shown to be transitive, so the claimed partial order may fail; this is a correctness/rigor issue, not a circular reduction, because the proof attempts to derive the partial order rather than assuming it. The paper also flags its own open questions and limitations (e.g., unknown NP-hardness for bounded tail size, and the chemically questionable treatment of cyclizations), which further argues against any hidden circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted free parameters and no invented entities. Its main load-bearing inputs are the assembly space definition from the prior literature and standard mathematical tools (B-hyperpaths, Szpilrajn's theorem, undecidability of DPO termination).

assumptions (4)
  • domain assumption The assembly space model of [43] (grounded, acyclic, edge-labeled multigraphs with symmetric labeling) is the correct formalization of assembly theory.
    The entire B-hypergraph translation in Section 2.1 starts from this model; if the model is wrong, the correspondence is moot.
  • standard math Definition of B-hyperpath from [10] (minimal w.r.t. vertex and edge deletion, with a linear order of edges).
    Used as the target notion in Section 2.2; the equivalence between assembly pathways and B-hyperpaths relies on this definition.
  • standard math Szpilrajn's theorem: every partial order extends to a total order.
    Used in Section 2.3 to linearize the reachability partial order for the CFG construction.
  • standard math Undecidability of DPO rewriting termination [46].
    Used in Section 3.4 to argue reachability is hard in general; this is a known result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Assembly in Directed Hypergraphs." pith.science (2026). https://pith.science/paper/RFWLO7BT

@misc{pith2026250522826,
  author       = {Pith},
  title        = {Pith review of: Assembly in Directed Hypergraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RFWLO7BT}},
  note         = {Machine review of arXiv:2505.22826}
}
read the original abstract

Assembly theory has received considerable attention in the recent past. Here we analyze the formal framework of this model and show that assembly pathways coincide with certain minimal hyperpaths in B-hypergraphs. This makes it possible to generalize the notion of assembly to general chemical reaction systems and to make explicit the connection to rule based models of chemistry, in particular DPO graph rewriting. We observe, furthermore, that assembly theory is closely related to retrosynthetic analysis in chemistry. The assembly index fits seamlessly into a large family of cost measures for directed hyperpath problems that also encompasses cost functions used in computational synthesis planning. This allows to devise a generic approach to compute complexity measures derived from minimal hyperpaths in rule-derived directed hypergraphs using integer linear programming.

Figures

Figures reproduced from arXiv: 2505.22826 by the authors.

Figure 2
Figure 2. Molecular structures resulting from iterative inverted cyclization to cubane; 4 leftmost: all of them have (like cubane) a molecular assembly index of 4; rightmost: molecular assembly index of 5 Since cyclizations in a witness pathways do not contribute to the assembly index, many chemically distinct compounds share the same index. For example, cubane has a cyclomatic number of five, requiring five vertex identifica… view at source ↗
Figure 3
Figure 3. DPO diagram, DPO Rule (top span) and an exem￾plification of its application to butanol - butanol is split into two compounds, leading to an inverse affixation (however, note, that the number of carbons does not remain invariant); the rule is the only rule needed to expand the chemical space which is expanded to find optimal solutions w.r.t. optimal assembly index 5.2. ILP Formulation. In the following we describe an… view at source ↗

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Historical Contingencies Steer the Topology of Randomly Assembled Graphs

    physics.soc-ph 2025-07 conditional novelty 7.0 of 10

    A recursive graph-merging algorithm produces networks with extreme topological properties that their degree sequences do not predict.

Reference graph

Works this paper leans on

59 extracted references · 57 canonical work pages · cited by 1 Pith paper

  1. [1]

    assembly theory

    D. L. Abel. “assembly theory” in life-origin models: A critical review.BioSystems, 247:105378, 2025

    work page 2025

  2. [2]

    F. S. Abrah˜ ao, S. Hern´ andez-Orozco, N. A. Kiani, J. Tegn´ er, and H. Zenil. Assembly theory is an approximation to algorithmic complexity based on LZ compression that does not explain selection or evolution.PLoS Complex Syst., 1, 2024

    work page 2024

  3. [3]

    J. L. Andersen, S. Banke, R. Fagerberg, C. Flamm, D. Merkle, and P. F. Stadler. On the realisability of chemical pathways. In X. Guo, S. Mangul, M. Patterson, and A. Zelikovsky, editors,ISBRA 2023: Bioinformatics Research and Applications, volume 14248 ofLect. Notes Comp. Sci., pages 409–419, Singapore, 2023. Springer

    work page 2023

  4. [4]

    J. L. Andersen, S. Banke, R. Fagerberg, C. Flamm, D. Merkle, and P. F. Stadler. Pathway realizability in chemical networks.J. Comput. Biol., 32:164–187, 2025

    work page 2025

  5. [5]

    J. L. Andersen, C. Flamm, D. Merkle, and P. F. Stadler. Inferring chemical reaction patterns using graph grammar rule composition.J. Syst. Chem., 4:4, 2013

    work page 2013

  6. [6]

    J. L. Andersen, C. Flamm, D. Merkle, and P. F. Stadler. Generic strategies for chemical space exploration.Int. J. Comp. Biol. Drug Design, 7:225–258, 2014. ICIBM 2013 contribution

    work page 2014

  7. [7]

    J. L. Andersen, C. Flamm, D. Merkle, and P. F. Stadler. A software package for chemically inspired graph transformation. In R. Echahed and M. Minas, editors,Graph Transformation, ICGT 2016, volume 9761 ofLecture Notes Comp. Sci., pages 73–88, Berlin, Heidelberg, D,

    work page 2016

  8. [8]

    J. L. Andersen, C. Flamm, D. Merkle, and P. F. Stadler. An intermediate level of abstraction for computational systems chemistry.Phil. Trans. R. Soc. A, 375:20160354, 2017

    work page 2017

Show all 59 references
  1. [9]

    J. L. Andersen, C. Flamm, D. Merkle, and P. F. Stadler. Chemical transformation motifs — modelling pathways as integer hyperflows.IEEE/ACM Trans. Comp. Biol., 16:510–523, 2019

    2019

  2. [10]

    Ausiello, P

    G. Ausiello, P. G. Franciosa, and D. Frigioni. Partially dynamic maintenance of minimum weight hyperpaths.J. Discrete Algorithms, 3:27–46, 2005

    2005

  3. [11]

    W. Banzhaf. Artificial chemistries – towards constructive dynamical systems. InSelf- Formation Theory and Applications, volume 97 ofSolid State Phenomena, pages 43–50. Trans Tech Publications Ltd, 2004

    2004

  4. [12]

    Benk¨ o, C

    G. Benk¨ o, C. Flamm, and P. F. Stadler. A graph-based toy model of chemistry.J. Chem. Inf. Comput. Sci., 43:1085–1093, 2003

    2003

  5. [13]

    S. H. Bertz and T. J. Sommer. Application of graph theory to synthesis planning: Com- plexity, reflexivity and vulnerability. In T. Hudlicky, editor,Organic Synthesis: Theory and Applications, pages 67–92. JAI Press, Greenwich, 1993

    1993

  6. [14]

    Bieniawski, P

    W. Bieniawski, P. Masierak, A. Tomski, and S. Lukaszyk. Assembly theory – formalizing assembly spaces and discovering patterns and bounds. Technical report, preprint.org, 2024

    2024

  7. [15]

    Braakman and E

    R. Braakman and E. Smith. The compositional and evolutionary logic of metabolism.Physical biology, 10:011001, 2013

    2013

  8. [16]

    G. J. Chaitin. On the length of programs for computing finite binary sequences.J. ACM, 13:547–569, 1966

    1966

  9. [17]

    Charikar, E

    M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and A. Shelat. The smallest grammar problem.IEEE Trans. Information Theory, 51:2554–2576, 2005

    2005

  10. [18]

    E. J. Corey. General methods for the construction of complex molecules.Pure Appl. Chem., 14:19–38, 1967

    1967

  11. [19]

    E. J. Corey, W. J. Howe, H. W. Orf, D. A. Pensak, and G. Petersson. General methods of synthetic analysis. Strategic bond disconnections for bridged polycyclic structures.J. Am. Chem. Soc., 97(21):6116–6124, 1975

    1975

  12. [20]

    E. J. Corey and W. T. Wipke. Computer-assisted design of complex organic syntheses.Sci- ence, 166:178–192, 1969

    1969

  13. [21]

    J. C. de Pina.Applications of shortest path methods. PhD thesis, University of Amsterdam, 1995

    1995

  14. [22]

    Derksen and J

    H. Derksen and J. Weyman. Quiver representations.Notices Amer. Math. Soc., 52:200–206, 2005

    2005

  15. [23]

    Dittrich and P

    P. Dittrich and P. Speroni di Fenizio. Chemical organisation theory.Bull. Math. Biol., 69:1199–1231, 2007. 19

    2007

  16. [24]

    Fagerberg, C

    R. Fagerberg, C. Flamm, R. Kianian, D. Merkle, and P. F. Stadler. Finding thekbest synthesis plans.J. Cheminformatics, 10:19, 2018

    2018

  17. [25]

    the arrival of the fittest

    W. Fontana and L. W. Buss. “the arrival of the fittest”: Toward a theory of biological organization.Bull. Math. Biol., 56:1–64, 1994

    1994

  18. [26]

    Fontana and L

    W. Fontana and L. W. Buss. What would be conserved if ‘the tape were played twice’ ?Proc. Natl. Acad. Sci. USA, 91:757–761, 1994

    1994

  19. [27]

    Gallo, G

    G. Gallo, G. Longo, S. Pallottino, and S. Nguyen. Directed hypergraphs and applications. Discrete Appl. Math., 42:177–201, 1993

    1993

  20. [28]

    Gallo and M

    G. Gallo and M. Scutell` a. A note on minimum makespan assembly plans.European Journal of Operational Research, 142:309–320, 2002

    2002

  21. [29]

    M. E. Gonz´ alez Laffitte, N. Beier, N. Domschke, and P. F. Stadler. Comparison of atom maps.MATCH: Comm. Math. Comp. Chem., 90:75–102, 2023

    2023

  22. [30]

    R. M. Hazen, P. C. Burns, H. J. Cleaves II, R. T. Downs, S. V. Krivovichev, and M. L. Wong. Molecular assembly indices of mineral heteropolyanions: some abiotic molecules are as complex as large biomolecules.J. Royal Soc. Interface, 21:202306, 2024

    2024

  23. [31]

    J. B. Hendrickson. Systematic synthesis design. 6. Yield analysis and convergency.J Am Chem Soc, 99:5439–5450, 1977

    1977

  24. [32]

    J. B. Hendrickson, E. Braun-Keller, and G. A. Toczko. A logic for synthesis design.Tetrahe- dron, 37, Suppl. I:359–370, 1981

    1981

  25. [33]

    J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph.SIAM J. Comput., 16:359–366, 1987

    1987

  26. [34]

    G. F. Italiano and U. Nanni. Online maintenance of minimal directed hypergraphs. Technical report, Columbia University, 1989

    1989

  27. [35]

    J. Jaeger. Assembly theory: What it does and what it does not do.J. Mol. Evol., 92, 2024

    2024

  28. [36]

    Jirasek, A

    M. Jirasek, A. Sharma, J. R. Bame, S. H. M. Mehr, N. Bell, S. M. Marshall, C. Mathis, A. Macleod, . G. J. T. Cooper, M. Swart, R. Mollfulleda, and L. Cronin. Determining molec- ular complexity using assembly theory and spectroscopy. Technical Report 2302.13753, arXiv, 2023

    2023 arXiv

  29. [37]

    C. P. Kempes, M. Lachmann, A. Iannaccone, G. M. Fricke, M. R. Chowdhury, S. I. Walker, and L. Cronin. Assembly theory and its relationship with computational complexity. Technical Report 2406.12176, arXiv, 2024

    2024 arXiv

  30. [38]

    J. C. Kieffer and E. H. Yang. Grammar-based codes: a new class of universal lossless source codes.IEEE Trans Inf Theory, 46:737–754, 2000

    2000

  31. [39]

    Y. Liu, C. Mathis, M. D. Bajczyk, S. M. Marshall, L. Wilbraham, and L. Cronin. Exploring and mapping chemical space with molecular assembly trees.Science Advances, 7:eabj2465, 2021

    2021

  32. [40]

    S. Lloyd. Measures of complexity: a nonexhaustive list.IEEE Control Systems Magazine, 21:7–8, 2001

    2001

  33. [41]

    assembly theory and its relationship with computational complexity

    S. Lukaszyk. On the “assembly theory and its relationship with computational complexity”. IPI Letters, 3:157, 2025

    2025

  34. [42]

    S. M. Marshall, C. Mathis, E. Carrick, G. Keenan, G. J. T. Cooper, H. Graham, M. Craven, P. S. Gromski, D. G. Moore, S. I. Walker, and L. Cronin. Identifying molecules as biosigna- tures with assembly theory and mass spectrometry.Nat Commun., 12:3033, 2021

    2021

  35. [43]

    S. M. Marshall, D. G. Moore, A. R. G. Murray, S. I. Walker, and L. Cronin. Formalising the pathways to life using assembly spaces.Entropy, 24:884, 2022

    2022

  36. [44]

    S. M. Marshall, A. R. G. Murray, and L. Cronin. A probabilistic framework for identifying biosignatures using pathway complexity.Philos Trans A Math Phys Eng Sci, 375:20160342, 2017

    2017

  37. [45]

    L. R. Nielsen, K. A. Andersen, and D. Pretolani. Finding theKshortest hyperpaths.Com- puters & Operations Research, 32:1477–1497, 2005

    2005

  38. [46]

    D. Plump. Termination of graph rewriting is undecidable.Fundamenta Informaticae, 33:201– 209, 1998

    1998

  39. [47]

    Relund Nielsen and D

    L. Relund Nielsen and D. Pretolani. A remark on the definition of a B-hyperpath. Technical report, Department of Operations Research, University of Aarhus, 2001

    2001

  40. [48]

    A. Ritz, B. Avent, and T. M. Murali. Pathway analysis with signaling hypergraphs. IEEE/ACM Trans Comput Biol Bioinform., 14:1042–1055, 2017

    2017

  41. [49]

    W. Rytter. Grammar compression, LZ-encodings, and string algorithms with implicit input. In J. D ´ ıaz, J. Karhum¨ aki, A. Lepist¨ o, and D. Sannella, editors,Automata, Languages and 20 Programming ICALP 2004, volume 3142 ofLect. Notes Comp. Sci., pages 15–27, Berlin, Heidelberg, 2004

    2004

  42. [50]

    Smith, H

    E. Smith, H. J. Morowitz, and S. D. Copley.Core Metabolism as a Self-Organized System, chapter 20, pages 432–460. The MIT Press, 2008

    2008

  43. [51]

    Szpilrajn

    E. Szpilrajn. Sur l’extension de l’ordre partiel.Fundamenta Mathematicae, 16:386–389, 1930

    1930

  44. [52]

    Thakur and R

    M. Thakur and R. Tripathi. Linear connectivity problems in directed hypergraphs.Theor. Comp. Sci., 410:2592–2618, 2009

    2009

  45. [53]

    theory explains, quantifies selection, and evolution

    A. theory explains, quantifies selection, and evolution. Sharma, abhishek and cz´ egel, d´ aniel and lachmann, michael and kempes, christopher p. and walker, sara i. and cronin, leroy. Nature, 622:321–328, 2023

    2023

  46. [54]

    Uthamacumaran, F

    A. Uthamacumaran, F. S. Abrah˜ ao, N. A. Kiani, and H. Zenil. On the salient limitations of the methods of Assembly Theory and their classification of molecular biosignatures. Technical Report 2210.00901, arXiv, 2022

    2022 arXiv

  47. [55]

    G. ´E. Vl´ eduts. Concerning one system of classification and codification of organic reactions. Information Storage and Retrieval, 1(2-3):117–146, 1963

    1963

  48. [56]

    Z. Wang, W. Zhang, and B. Liu. Computational analysis of synthetic planning: Past and future.Chinese J. Chem., 39:3127–3143, 2021

    2021

  49. [57]

    A. V. Zeigarnik. On hypercycles and hypercircuits in hypergraphs. In P. Hansen, P. W. Fowler, and M. Zheng, editors,Discrete Mathematical Chemistry, volume 51 ofDIMACS series in discrete mathematics and theoretical computer science, pages 377–383, Providence, RI, 2000. America...

    2000

  50. [58]

    Ziv and A

    J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding.IEEE Trans. Inf. Theory, 24:530–536, 1978

    1978

  51. [59]

    optimal witness

    A. K. Zvonkin and L. A. Levin. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms.Russian Mathematical Surveys, 25:83–124, 1970. 21 5.Appendix This appendix introduces a graph transformation r...

    1970

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.