Skip to main content
Top

2018 | OriginalPaper | Chapter

The Computing Power of Determinism and Reversibility in Chemical Reaction Automata

Authors : Fumiya Okubo, Takashi Yokomori

Published in: Reversibility and Universality

Publisher: Springer International Publishing

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

search-config
loading …

Abstract

Chemical reaction automata (CRAs) are computing models with multiset storage based on multiset rewriting introduced in Okubo, Yokomori, (DNA20, LNCS, vol. 8727, pp. 53–66, (2014), [25]). A CRA consists of a finite set of reactions (or pairs of multisets called reactants and products, respectively) and an initial multiset as well as a set of final multisets. Taking an input symbol in the current configuration (multiset) a CRA changes it into a new configuration. Thus, a CRA offers an automaton-like computing model to investigate the computational analysis of chemical reactions. On the other hand, since any (irreversible) Turing machine was proven to be effectively simulated by a reversible Turing machine in Bennett, (IBM J Res Dev, 17(6), 525–532, (1973), [4]), reversible computing has become a research field that has been receiving increased attention. In this paper we introduce the notions of determinism and reversibility into CRAs, and investigate the computational powers of those classes of CRAs in comparison with the language classes of Chomsky hierarchy. The computing power of reversible CRAs involves the physical realization of molecular programming of chemical reaction networks (Thachuk, Condon, DNA 18, LNCS, vol. 7433, pp. 135–149, (2012), [32]) with DNA strand displacement system implementation (Qian, Winfree, Science, 332, 1196–1201, (2011), [29]), and therefore, it is of great significance to elucidate the computing capabilities of both deterministic and reversible CRAs from the theoretical viewpoint of molecular computing.

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!

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!

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!

Literature
2.
go back to reference Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Urn Automata. No.YLEU/DCS/TR-1280, Department of Computer Science, Yale University, New Haven CT, USA (2003) Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Urn Automata. No.YLEU/DCS/TR-1280, Department of Computer Science, Yale University, New Haven CT, USA (2003)
3.
go back to reference Alhazov, A., Freund, R., Morita, K.: Sequential and maximally parallel multiset rewriting: reversibility and determinism. Nat. Comput. 11, 95–106 (2012)MathSciNetCrossRefMATH Alhazov, A., Freund, R., Morita, K.: Sequential and maximally parallel multiset rewriting: reversibility and determinism. Nat. Comput. 11, 95–106 (2012)MathSciNetCrossRefMATH
5.
go back to reference Calude, C., Păun, Gh, Rozenberg, G.: In: Salomaa, A. (ed.) Multiset Processing. LNCS, vol. 2235. Springer, Heidelberg (2001) Calude, C., Păun, Gh, Rozenberg, G.: In: Salomaa, A. (ed.) Multiset Processing. LNCS, vol. 2235. Springer, Heidelberg (2001)
6.
go back to reference Csuhaj-Varju, E., Vaszil, G.: P Automata or Purely Communicating Accepting P Systems. LNCS, vol. 2597, pp. 219–233. Springer, Berlin (2003) Csuhaj-Varju, E., Vaszil, G.: P Automata or Purely Communicating Accepting P Systems. LNCS, vol. 2597, pp. 219–233. Springer, Berlin (2003)
7.
go back to reference Csuhaj-Varju, E., Vaszil, G.: P automata. In the Oxford Handbook of Membrane Computing, pp. 145–167. (2010) Csuhaj-Varju, E., Vaszil, G.: P automata. In the Oxford Handbook of Membrane Computing, pp. 145–167. (2010)
8.
go back to reference Daley, M., Eramian, M., McQuillan, I.: The bag automaton: a model of nondeterministic storage. J. Autom. Lang. Comb. 13, 185–206 (2008)MathSciNetMATH Daley, M., Eramian, M., McQuillan, I.: The bag automaton: a model of nondeterministic storage. J. Autom. Lang. Comb. 13, 185–206 (2008)MathSciNetMATH
11.
go back to reference Hopcroft, J.E., Motwani, T., Ullman, J.D.: Introduction to automata theory, language and computation, 2nd edn. Addison-Wesley, Reading (2003)MATH Hopcroft, J.E., Motwani, T., Ullman, J.D.: Introduction to automata theory, language and computation, 2nd edn. Addison-Wesley, Reading (2003)MATH
12.
13.
go back to reference Kudlek, M., Martin-Vide, C., Păun, Gh: Toward a formal macroset theory. In: Calude, C., Păun, Gh, Rozenberg, G., Salomaa, A. (eds.) Multiset Processing. LNCS, vol. 2235, pp. 123–133. Springer, Berlin (2001) Kudlek, M., Martin-Vide, C., Păun, Gh: Toward a formal macroset theory. In: Calude, C., Păun, Gh, Rozenberg, G., Salomaa, A. (eds.) Multiset Processing. LNCS, vol. 2235, pp. 123–133. Springer, Berlin (2001)
16.
go back to reference Leporati, A., Zandron, C., Mauri, G.: Reversible P systems to simulate Fredkin circuits. Fundam. Inform. 74, 529–548 (2006)MathSciNetMATH Leporati, A., Zandron, C., Mauri, G.: Reversible P systems to simulate Fredkin circuits. Fundam. Inform. 74, 529–548 (2006)MathSciNetMATH
17.
go back to reference Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible turing machines. Trans. IEICE Japan E72(3), 223–228 (1989) Morita, K., Shirasaki, A., Gono, Y.: A 1-tape 2-symbol reversible turing machines. Trans. IEICE Japan E72(3), 223–228 (1989)
20.
go back to reference Morita, K.: Two-way reversible multi-head finite automata. Fundam. Inform. 110(1–4), 241–254 (2011)MathSciNetMATH Morita, K.: Two-way reversible multi-head finite automata. Fundam. Inform. 110(1–4), 241–254 (2011)MathSciNetMATH
21.
go back to reference Nishida, T.Y.: Reversible P systems with symport/antiport Rules. In: Proceedings of the 10th Workshop on Membrane Computing, pp. 452–460 (2009) Nishida, T.Y.: Reversible P systems with symport/antiport Rules. In: Proceedings of the 10th Workshop on Membrane Computing, pp. 452–460 (2009)
24.
go back to reference Okubo, F., Kobayashi, S., Yokomori, T.: On the properties of language classes defined by bounded reaction automata. Theor. Comput. Sci. 454, 206–221 (2012)MathSciNetCrossRefMATH Okubo, F., Kobayashi, S., Yokomori, T.: On the properties of language classes defined by bounded reaction automata. Theor. Comput. Sci. 454, 206–221 (2012)MathSciNetCrossRefMATH
25.
go back to reference Okubo, F., Yokomori, T.: The computational capability of chemical reaction automata. In: Murata, S., Kobayashi, S. (eds.) DNA20. LNCS, vol. 8727, pp. 53–66. Springer, Switzerland (2014). Also, in Natural Computing, vol. 15, pp. 215–224. (2016) Okubo, F., Yokomori, T.: The computational capability of chemical reaction automata. In: Murata, S., Kobayashi, S. (eds.) DNA20. LNCS, vol. 8727, pp. 53–66. Springer, Switzerland (2014). Also, in Natural Computing, vol. 15, pp. 215–224. (2016)
26.
go back to reference Paun, G., Rozenberg, G., Salomaa, A.: The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York (2010) Paun, G., Rozenberg, G., Salomaa, A.: The Oxford Handbook of Membrane Computing. Oxford University Press, Inc., New York (2010)
27.
go back to reference Peterson, J.L.: Petri Net Theory and the Modelling of Systems. Prentice-Hall, Englewood Cliffs (1981) Peterson, J.L.: Petri Net Theory and the Modelling of Systems. Prentice-Hall, Englewood Cliffs (1981)
28.
go back to reference Pin, J.E.: On Reversible Automata. In: Proceedings of LATIN ’92, 1st Latin American Symposium on Theoretical Informatics, São Paulo, Brazil, April 6-10, pp. 401–416 (1992) Pin, J.E.: On Reversible Automata. In: Proceedings of LATIN ’92, 1st Latin American Symposium on Theoretical Informatics, São Paulo, Brazil, April 6-10, pp. 401–416 (1992)
29.
go back to reference Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades. Science 332, 1196–1201 (2011)CrossRef Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades. Science 332, 1196–1201 (2011)CrossRef
30.
go back to reference Qian, L., Soloveichik, D., Winfree, E.: Efficient turing-universal computation with DNA polymers. In: Sakakibara, Y., Mi, Y. (eds.) DNA16. LNCS, vol. 6518, pp. 123–140. Springer, Heidelberg (2011) Qian, L., Soloveichik, D., Winfree, E.: Efficient turing-universal computation with DNA polymers. In: Sakakibara, Y., Mi, Y. (eds.) DNA16. LNCS, vol. 6518, pp. 123–140. Springer, Heidelberg (2011)
31.
go back to reference Rozenberg, G., Back, T.: Section IV: molecular computation. In: Kok, J.N. (ed.) Handbook of Natural Computing, vol. 3, pp. 1071–1355. Springer, Berlin (2012) Rozenberg, G., Back, T.: Section IV: molecular computation. In: Kok, J.N. (ed.) Handbook of Natural Computing, vol. 3, pp. 1071–1355. Springer, Berlin (2012)
32.
go back to reference Thachuk, C., Condon, A.: In: Stefanovic, D., Turberfield, A. (eds.) Space and energy efficient computation with DNA strand displacement systems. DNA 18. LNCS, vol. 7433, pp. 135–149. Springer, Heidelberg (2012) Thachuk, C., Condon, A.: In: Stefanovic, D., Turberfield, A. (eds.) Space and energy efficient computation with DNA strand displacement systems. DNA 18. LNCS, vol. 7433, pp. 135–149. Springer, Heidelberg (2012)
33.
Metadata
Title
The Computing Power of Determinism and Reversibility in Chemical Reaction Automata
Authors
Fumiya Okubo
Takashi Yokomori
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-73216-9_13

Premium Partner