Top

Published in:

2023 | OriginalPaper | Chapter

Computational Complexity of Reversible Reaction Systems

Authors : Markus Holzer, Christian Rauch

Published in: Reversible Computation

Publisher: Springer Nature Switzerland

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

search-config

AI-assisted search

Off

Abstract

The computational complexity of problems related to reaction systems (RSs) such as, e.g., reachability, simulation, etc., are well understood. We investigate the complexity of some of these problems for reversible RSs. Since some of the computational complexity (lower bound) proofs in the general case rely on reductions from Turing machine problems here the main challenge is to present constructions that ensure the reversibility of the RS that encodes Turing machine configurations by sets, which allows ambiguous representation. For the problems under consideration we can show that there is no difference in complexity for reversible RSs compared to the general case. One exception is the question of the existence of a reversible subcomputation.

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 "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

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

previous chapter Towards a Taxonomy for Reversible Computation Approaches

next chapter Optimization of Reversible Control Flow Graphs

Azimi, S., Iancu, B., Petre, I.: Reaction system models for the heat shock response. Fund. Inform. 131(3–4), 299–312 (2014)MathSciNetMATH

Bagossy, A., Vaszil, G.: Simulating reversible computation with reaction systems. J. Membrane Comput. 2, 179–193 (2020)MathSciNetCrossRefMATH

Cienciala, L., Ciencialová, L., Csuhaj-Varjú, E.: About reversibility in SP colonies and reaction systems. Natural Comput., October (2022)

Dennunzio, A., Formenti, E., Manzoni, L.: Reaction systems and extremal combinatorics properties. Theor. Comput. Sci. 598, 138–149 (2015)MathSciNetCrossRefMATH

Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A.E.: Complexity of the dynamics of reaction systems. Inf. Comput. 267, 96–109 (2019)MathSciNetCrossRefMATH

Ehrenfeucht, A., Kleijn, J., Koutny, M., Rozenberg, G.: Minimal reaction systems. In: Priami, C., Petre, I., de Vink, E. (eds.) Transactions on Computational Systems Biology XIV. LNCS, vol. 7625, pp. 102–122. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35524-0_5CrossRefMATH

Ehrenfeucht, A., Rozenberg, G.: Reaction systems. Fund. Inform. 75, 263–280 (2007)MathSciNetMATH

Galil, Z.: Hierarchies of complete problems. Acta Informatica 6(1), 77–88 (1976). https://doi.org/10.1007/BF00263744MathSciNetCrossRefMATH

Holzer, M., Rauch, C.: On the computational complexity of reaction systems, revisited. In: Santhanam, R., Musatov, D. (eds.) CSR 2021. LNCS, vol. 12730, pp. 170–185. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-79416-3_10CrossRef

10.

Lange, K.-J., McKenzie, P., Tapp, A.: Reversible space equals deterministic space. J. Comput. Syst. Sci. 60(2), 354–367 (2000)MathSciNetCrossRefMATH

11.

Manzoni, L., Poças, D., Porreca, A.E.: Simple reaction systems and their classification. Int. J. Found. Comput. Sci. 25(4), 441–457 (2014)MathSciNetCrossRefMATH

12.

Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)

13.

Salomaa, A.: Functions and sequences generated by reaction systems. Theor. Comput. Sci. 466, 87–96 (2012)MathSciNetCrossRefMATH

14.

Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177–192 (1970)MathSciNetCrossRefMATH

15.

Sipser, M.: Halting space-bounded computations. Theor. Comput. Sci. 10, 335–338 (1980)MathSciNetCrossRefMATH

16.

Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Proceedings of the 5th Symposium on Theory of Computing, pp. 1–9 (1973)

17.

Teh, W.C., Atanasiu, A.: Minimal reaction system revisited and reaction system rank. Int. J. Found. Comput. Sci. 28(3), 247–261 (2017)MathSciNetCrossRefMATH

Title: Computational Complexity of Reversible Reaction Systems
Authors: Markus Holzer
Christian Rauch
Publisher: Springer Nature Switzerland
Book: Reversible Computation
Print ISBN: 978-3-031-38099-0

Electronic ISBN: 978-3-031-38100-3

Copyright Year: 2023
DOI: https://doi.org/10.1007/978-3-031-38100-3_4

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner