nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Computational Complexity of Reversible Reaction Systems

verfasst von : Markus Holzer, Christian Rauch

Erschienen in: Reversible Computation

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Towards a Taxonomy for Reversible Computation Approaches

Nächstes Kapitel 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

Titel: Computational Complexity of Reversible Reaction Systems
verfasst von: Markus Holzer
Christian Rauch
Verlag: Springer Nature Switzerland
Buch: Reversible Computation
Print ISBN: 978-3-031-38099-0

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

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

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner