Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
DE
EN
Books
Journals
Events
Topic Page
Marketing
Log in
Learn more about individual access
Request company access
Electric Powertrains and Energy Systems 2025 | 26 + 27 March 2025

19th International MTZ Congress on Future Powertrains

Take this opportunity to attend the conference. Experts from the automotive industry, energy providers, and grid operators will meet up with representatives from politics and science to discuss important topics for this sector.
EXTENDED SEARCH
Log in
Top
New Generation Computing
Published in:

04-06-2024 | Research Paper

A Cellular Automaton Approach for Efficient Computing on Surface Chemical Reaction Networks

Authors: Sihai Yu, Wenli Xu, Jia Lee, Teijiro Isokawa

Published in: New Generation Computing | Issue 2/2024

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

A surface chemical reaction network (sCRN, Qian and Winfree in DNA Computing and Molecular Programming: 20th International Conference, DNA 20, Kyoto, Japan, September 22–26, 2014. Proceedings 20. Springer, 2014) is an emergent paradigm for molecular programming, in which a chemical molecule is placed at each site of a lattice, and each molecule may undergo either bi-molecular reactions associated with one of the nearest molecules or uni-molecular reactions autonomously. The lattice structure as well as the localized reactions between molecules facilitate an effective formalization of sCRNs in the framework of cellular automata. This formalism not only allows a systematic evaluation of the complexity of a sCRN, but also enables a formal approach to reduce the model’s complexity for the sake of improving its effectiveness. To this end, this paper proposes a new sCRN model that has less complexity measured in terms of the numbers of both cell states and transition rules. Especially, universality of computations will be shown by implementing all asynchronous circuits, including the well-known full-adder, into the sCRN. The decreased complexity may enhance the feasibility of the proposed sCRN model for physical implementation.
previous article Networks of Classical Conditioning Gates and Their Learning
next article Characterization of Cascaded DNA Generation Reaction for Amplifying DNA Signal

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Keyes, R.W.: Physical limits of silicon transistors and circuits. Rep. Prog. Phys. 68(12), 2701 (2005)CrossRef
2.
Markov, I.L.: Limits on fundamental limits to computation. Nature 512(7513), 147–154 (2014)CrossRef
3.
Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266(5187), 1021–1024 (1994)CrossRef
4.
Benenson, Y.: Biomolecular computing systems: principles, progress and potential. Nat. Rev. Genet. 13(7), 455–468 (2012)CrossRef
5.
Li, J., Green, A.A., Yan, H., Fan, C.: Engineering nucleic acid structures for programmable molecular circuitry and intracellular biocomputation. Nat. Chem. 9(11), 1056–1067 (2017)CrossRef
6.
Okubo, F., Fujioka, K., Yokomori, T.: Chemical reaction regular grammars. New Gener. Comput. 40(2), 659–680 (2022)CrossRef
7.
Kawamata, I., Nomura, S.-I.M., Murata, S.: Autonomous and programmable strand generator implemented as DNA and enzymatic chemical reaction cascade. New Gener. Comput. 40(2), 723–736 (2022)CrossRef
8.
Bath, J., Turberfield, A.J.: DNA nanomachines. Nat. Nanotechnol. 2(5), 275–284 (2007)CrossRef
9.
Seeman, N.C., Sleiman, H.F.: DNA nanotechnology. Nat. Rev. Mater. 3(1), 1–23 (2017)CrossRef
10.
Hori, Y., Kantak, C., Murray, R.M., Abate, A.R.: Cell-free extract based optimization of biomolecular circuits with droplet microfluidics. Lab Chip 17(18), 3037–3042 (2017)CrossRef
11.
Sakurai, Y., Hori, Y.: Optimization-based synthesis of stochastic biocircuits with statistical specifications. J. R. Soc. Interface 15(138), 20170709 (2018)CrossRef
12.
Murata, S., Konagaya, A., Kobayashi, S., Saito, H., Hagiya, M.: Molecular robotics: a new paradigm for artifacts. New Gener. Comput. 31, 27–45 (2013)CrossRef
13.
Nakakuki, T., Imura, J.-i: Molecular governor: DNA feedback regulator for molecular robotics. SICE J. Control Meas. Syst. Integr. 9(2), 60–69 (2016)CrossRef
14.
Qian, L., Winfree, E., Bruck, J.: Neural network computation with DNA strand displacement cascades. Nature 475(7356), 368–372 (2011)CrossRef
15.
Cherry, K.M., Qian, L.: Scaling up molecular pattern recognition with DNA-based winner-take-all neural networks. Nature 559(7714), 370–376 (2018)CrossRef
16.
Cook, M., Soloveichik, D., Winfree, E., Bruck, J.: Programmability of chemical reaction networks. In: Algorithmic Bioprocesses, pp. 543–584. Springer (2009)
17.
Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7, 615–633 (2008)MathSciNetCrossRef
18.
Joshi, B., Shiu, A.: Atoms of multistationarity in chemical reaction networks. J. Math. Chem. 51, 153–178 (2013)MathSciNet
19.
20.
Anderson, D.F., Kurtz, T.G.: Continuous time Markov chain models for chemical reaction networks. In: Design and Analysis of Biomolecular Circuits: Engineering Approaches to Systems and Synthetic Biology, pp. 3–42. Springer (2011)
21.
Gorban, A.N., Radulescu, O., Zinovyev, A.Y.: Asymptotology of chemical reaction networks. Chem. Eng. Sci. 65(7), 2310–2324 (2010)CrossRef
22.
Doty, D.: Timing in chemical reaction networks. In: Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 772–784. SIAM (2014)
23.
Fages, F., Le Guludec, G., Bournez, O., Pouly, A.: Strong Turing completeness of continuous chemical reaction networks and compilation of mixed analog-digital programs. In: Computational Methods in Systems Biology: 15th International Conference, CMSB 2017, Darmstadt, Germany, September 27–29, 2017, Proceedings 15, pp. 108–127. Springer (2017)
24.
Qu, X., Wang, S., Ge, Z., Wang, J., Yao, G., Li, J., Zuo, X., Shi, J., Song, S., Wang, L., et al.: Programming cell adhesion for on-chip sequential boolean logic functions. J. Am. Chem. Soc. 139(30), 10176–10179 (2017)CrossRef
25.
Wen, M., Spotte-Smith, E.W.C., Blau, S.M., McDermott, M.J., Krishnapriyan, A.S., Persson, K.A.: Chemical reaction networks and opportunities for machine learning. Nat. Comput. Sci. 1–13 (2023)
26.
Bennett, C.H.: The thermodynamics of computation-a review. Int. J. Theor. Phys. 21, 905–940 (1982)CrossRef
27.
Qian, L., Soloveichik, D., Winfree, E.: Efficient Turing-universal computation with DNA polymers. In: DNA Computing and Molecular Programming: 16th International Conference, DNA 16, Hong Kong, China, June 14–17, 2010, Revised Selected Papers 16, pp. 123–140. Springer (2011)
28.
Qian, L., Winfree, E.: Parallel and scalable computation and spatial dynamics with DNA-based chemical reaction networks on a surface. In: DNA Computing and Molecular Programming: 20th International Conference, DNA 20, Kyoto, Japan, September 22-26, 2014. Proceedings 20, pp. 114–131. Springer (2014)
29.
Clamons, S., Qian, L., Winfree, E.: Programming and simulating chemical reaction networks on a surface. J. R. Soc. Interface 17(166), 20190790 (2020)CrossRef
30.
Doty, D.: Theory of algorithmic self-assembly. Commun. ACM 55(12), 78–88 (2012)CrossRef
31.
Ma, X., Lombardi, F.: Synthesis of tile sets for DNA self-assembly. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 27(5), 963–967 (2008)CrossRef
32.
Seki, S., Winslow, A.: The complexity of fixed-height patterned tile self-assembly. Int. J. Found. Comput. Sci. 28(05), 465–482 (2017)MathSciNetCrossRef
33.
34.
Peper, F., Lee, J., Carmona, J., Cortadella, J., Morita, K.: Brownian circuits: fundamentals. ACM J. Emerg. Technol. Comput. Syst. (JETC) 9(1), 1–24 (2013)CrossRef
35.
Lee, J., Peper, F., Leibnitz, K., Gu, P.: Characterization of random fluctuation-based computation in cellular automata. Inf. Sci. 352–353, 150–166 (2016)CrossRef
36.
Fatès, N.: A guided tour of asynchronous cellular automata. J. Cell. Autom. 9(5–6), 387–416 (2014)MathSciNet
37.
von Neumann, J.: Theory of self-reproducing automata. In: Burks A.W. (Eds.) (1966)
38.
39.
Schönfisch, B., de Roos, A.: Synchronous and asynchronous updating in cellular automata. BioSystems 51(3), 123–143 (1999)CrossRef
40.
Moreira, A., Boccara, N., Goles, E.: On conservative and monotone one-dimensional cellular automata and their particle representation. Theor. Comput. Sci. 325, 285–316 (2004)MathSciNetCrossRef
41.
42.
43.
44.
Lee, J., Peper, F., Adachi, S., Morita, K.: Universal delay-insensitive circuits with bi-directional and buffering lines. IEEE Trans. Comput. 53(8), 1034–1046 (2004)CrossRef
45.
Martin, A.J., Nystrom, M.: Asynchronous techniques for system-on-chip design. Proc. IEEE 94(6), 1089–1120 (2006)CrossRef
46.
Patra, P., Fussell, D.S.: A framework for conservative and delay-insensitive computing. In: Proc. Workshop on Physics and Computation (PhysComp’96), Boston, MA, United States, pp. 248–259 (1996)
47.
Lee, J., Peper, F., Cotofana, S.D., Naruse, M., Ohtsu, M., Kawazoe, T., Takahashi, Y., Shimokawa, T., Kish, L.B., Kubota, T.: Brownian circuits: designs. Int. J. Unconv. Comput. 12(5–6), 341–362 (2016)
48.
Banks, E.R.: Universality in cellular automata. In: 11th Annual Symposium on Switching and Automata Theory (swat 1970), pp. 194–215. IEEE (1970)
49.
Lee, J., Adachi, S., Peper, F., Morita, K.: Embedding universal delay-insensitive circuits in asynchronous cellular spaces. Fundam. Inform. 58(3–4), 295–320 (2003)MathSciNet
50.
Schneider, O., Worsch, T.: A 3-state asynchronous ca for the simulation of delay-insensitive circuits. In: Cellular Automata: 10th International Conference on Cellular Automata for Research and Industry, ACRI 2012, Santorini Island, Greece, September 24-27, 2012. Proceedings 10, pp. 565–574. Springer (2012)
51.
Lee, J., Peper, F.: On Brownian cellular automata. In: Adamatzky, A., Alonso-Sanz, R., Lawniczak, A., Martinez, G. J., Morita, K., and Worsch, T. (eds.) Theory and Application of Cellular Automata, pp. 278–291. Luniver Press (2008)
52.
Hutton, T.J.: Evolvable self-reproducing cells in a two-dimensional artificial chemistry. Artif. Life 13(1), 11–30 (2007)MathSciNetCrossRef
53.
Xu, W., Wu, C., Peng, Q., Lee, J., Xia, Y., Kawasaki, S.: Enhancing the diversity of self-replicating structures using active self-adapting mechanisms. Front. Genet. 13, 958069 (2022)CrossRef
Metadata
Title
A Cellular Automaton Approach for Efficient Computing on Surface Chemical Reaction Networks
Authors
Sihai Yu
Wenli Xu
Jia Lee
Teijiro Isokawa
Publication date
04-06-2024
Publisher
Springer Japan
Published in
New Generation Computing / Issue 2/2024
Print ISSN: 0288-3635
Electronic ISSN: 1882-7055
DOI
https://doi.org/10.1007/s00354-024-00262-5

Other articles of this Issue 2/2024

Preface: Special Issue on Molecular Cybernetics: Theory and Practice Toward Chemical AI

  • Preface

Correlation Between In Vitro and In Vivo Gene-Expression Strengths is Dependent on Bottleneck Process

  • Open Access
  • Research Paper

Networks of Classical Conditioning Gates and Their Learning

  • Open Access
  • Research Paper

Analysis of Signal Distortion in Molecular Communication Channels Using Frequency Response

  • Research Paper

On-Line Reoptimization of Mammalian Fed-Batch Culture Using a Nonlinear Model Predictive Controller

Characterization of Cascaded DNA Generation Reaction for Amplifying DNA Signal

  • Research Paper

Premium Partner

    Image Credits