Computation in chemical graph rewriting networks
Biological systems are frequently viewed as performing computations that are implemented by chemical transformations underlying the turn-over of their molecular components. In chemical reaction networks, computation may refer to at least two fundamentally different aspects: concentrations of molecul...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2025-01-01
|
| Series: | Journal of Physics: Complexity |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/2632-072X/adb7b1 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850075299298934784 |
|---|---|
| author | Christoph Flamm Daniel Merkle Peter F Stadler |
| author_facet | Christoph Flamm Daniel Merkle Peter F Stadler |
| author_sort | Christoph Flamm |
| collection | DOAJ |
| description | Biological systems are frequently viewed as performing computations that are implemented by chemical transformations underlying the turn-over of their molecular components. In chemical reaction networks, computation may refer to at least two fundamentally different aspects: concentrations of molecules, and molecular structures. The latter can be captured by modeling chemical reactions as a rewriting system acting on structural formulae, i.e. labeled graphs. We investigate the computational power of double-pushout (DPO) graph rewriting restricted to chemical graphs and show that chemical graph rewriting is sufficient to emulate Turing machines and two-tag systems on polymeric graphs that act as tapes. Moreover, we raise the question whether chemistry, modeled as DPO graph rewriting together with some additional form of chemical programs, may be computationally universal in the strong sense, i.e. capable of computing any computable function on chemical graphs. |
| format | Article |
| id | doaj-art-904bfe6ad8a04df7bed391772b7b75aa |
| institution | DOAJ |
| issn | 2632-072X |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | Journal of Physics: Complexity |
| spelling | doaj-art-904bfe6ad8a04df7bed391772b7b75aa2025-08-20T02:46:20ZengIOP PublishingJournal of Physics: Complexity2632-072X2025-01-016101501410.1088/2632-072X/adb7b1Computation in chemical graph rewriting networksChristoph Flamm0https://orcid.org/0000-0001-5500-2415Daniel Merkle1https://orcid.org/0000-0001-7792-375XPeter F Stadler2https://orcid.org/0000-0002-5016-5191Department of Theoretical Chemistry, University of Vienna , Währinger Straße 17, A-1090 Wien, AustriaAlgorithmic Cheminformatics Group, Faculty of Technology, Bielefeld University , D-33615 Bielefeld, Germany; Department of Mathematics and Computer Science, Faculty of Science, University of Southern Denmark , Odense M DK-5230, DenmarkDepartment of Theoretical Chemistry, University of Vienna , Währinger Straße 17, A-1090 Wien, Austria; Bioinformatics Group, Department of Computer Science, Interdisciplinary Center for Bioinformatics, Zuse School of Embedded and Composite AI (SECAI) Dresden-Leipzig, and Center for Scalable Data Analytics and Artificial Intelligence (ScaDS.AI) Dresden-Leipzig, University Leipzig , D-04107 Leipzig, Germany; Max Planck Institute for Mathematics in the Sciences , D-04103 Leipzig, Germany; Facultad de Ciencias, Universidad Nacional de Colombia , Sede Bogotá, Ciudad Universitaria, COL-111321 Bogotá, D.C., Colombia; Santa Fe Institute , Santa Fe, NM 87501, United States of AmericaBiological systems are frequently viewed as performing computations that are implemented by chemical transformations underlying the turn-over of their molecular components. In chemical reaction networks, computation may refer to at least two fundamentally different aspects: concentrations of molecules, and molecular structures. The latter can be captured by modeling chemical reactions as a rewriting system acting on structural formulae, i.e. labeled graphs. We investigate the computational power of double-pushout (DPO) graph rewriting restricted to chemical graphs and show that chemical graph rewriting is sufficient to emulate Turing machines and two-tag systems on polymeric graphs that act as tapes. Moreover, we raise the question whether chemistry, modeled as DPO graph rewriting together with some additional form of chemical programs, may be computationally universal in the strong sense, i.e. capable of computing any computable function on chemical graphs.https://doi.org/10.1088/2632-072X/adb7b1chemical reaction networksdouble pushout graph rewritingTuring machinetwo-tag systemchemical graph rewritingstrong computational completeness |
| spellingShingle | Christoph Flamm Daniel Merkle Peter F Stadler Computation in chemical graph rewriting networks Journal of Physics: Complexity chemical reaction networks double pushout graph rewriting Turing machine two-tag system chemical graph rewriting strong computational completeness |
| title | Computation in chemical graph rewriting networks |
| title_full | Computation in chemical graph rewriting networks |
| title_fullStr | Computation in chemical graph rewriting networks |
| title_full_unstemmed | Computation in chemical graph rewriting networks |
| title_short | Computation in chemical graph rewriting networks |
| title_sort | computation in chemical graph rewriting networks |
| topic | chemical reaction networks double pushout graph rewriting Turing machine two-tag system chemical graph rewriting strong computational completeness |
| url | https://doi.org/10.1088/2632-072X/adb7b1 |
| work_keys_str_mv | AT christophflamm computationinchemicalgraphrewritingnetworks AT danielmerkle computationinchemicalgraphrewritingnetworks AT peterfstadler computationinchemicalgraphrewritingnetworks |