Templated Assembly Theory: An Extension of the Canonical Assembly Index with Block-Compressed Template
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908813984006144 |
|---|---|
| author | Masierak, Piotr |
| author_facet | Masierak, Piotr |
| contents | Assembly Theory, as developed by Cronin and co-workers, assigns to an object an assembly index: the minimal number of binary join operations required to build at least one copy of the object from a specified set of basic building blocks, allowing reuse of intermediate components. For strings over a finite alphabet, the canonical assembly index can be defined in the free semigroup with universal binary concatenation and a "no-trash" condition, and its exact computation has been shown to be NP-complete. In this paper we propose an extension of the canonical, string-based formulation which augments pure concatenation with templated assembly steps. Intermediate objects may contain a distinguished wildcard symbol that represents a compressible block. Templates are restricted to block-compressed substrings of the target string and can be instantiated by inserting previously assembled motifs into one or many wildcard positions, possibly in parallel. This yields a new complexity measure, the templated assembly index, which strictly generalises the canonical index while preserving its operational character. We formalise the model, clarify its relation to the canonical assembly index and to classical problems such as the smallest grammar problem, and discuss the computational complexity of determining the templated assembly index. Finally, we sketch potential applications in sequence analysis, modularity detection, and biosignature design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_04889 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Templated Assembly Theory: An Extension of the Canonical Assembly Index with Block-Compressed Template Masierak, Piotr Formal Languages and Automata Theory 68W32 (Primary) 68R15, 68R10 (Secondary) G.2; F.2.2 Assembly Theory, as developed by Cronin and co-workers, assigns to an object an assembly index: the minimal number of binary join operations required to build at least one copy of the object from a specified set of basic building blocks, allowing reuse of intermediate components. For strings over a finite alphabet, the canonical assembly index can be defined in the free semigroup with universal binary concatenation and a "no-trash" condition, and its exact computation has been shown to be NP-complete. In this paper we propose an extension of the canonical, string-based formulation which augments pure concatenation with templated assembly steps. Intermediate objects may contain a distinguished wildcard symbol that represents a compressible block. Templates are restricted to block-compressed substrings of the target string and can be instantiated by inserting previously assembled motifs into one or many wildcard positions, possibly in parallel. This yields a new complexity measure, the templated assembly index, which strictly generalises the canonical index while preserving its operational character. We formalise the model, clarify its relation to the canonical assembly index and to classical problems such as the smallest grammar problem, and discuss the computational complexity of determining the templated assembly index. Finally, we sketch potential applications in sequence analysis, modularity detection, and biosignature design. |
| title | Templated Assembly Theory: An Extension of the Canonical Assembly Index with Block-Compressed Template |
| topic | Formal Languages and Automata Theory 68W32 (Primary) 68R15, 68R10 (Secondary) G.2; F.2.2 |
| url | https://arxiv.org/abs/2602.04889 |