Top

Natural Computing

24-02-2024

Ranks of functions specified by minimal reaction systems and induced by images of singletons

Authors: Husain Intekhab, Wen Chean Teh

Published in: Natural Computing

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

search-config

AI-assisted search

Off

Abstract

This paper studies mathematical properties of reaction systems, which is a formal model introduced by Ehrenfeucht and Rozenberg and inspired by biochemical reactions that occur in living cells. Numerous studies have focused on reaction system ranks of functions specified by minimal reaction systems, where the rank refers to the smallest size among the specifying reaction systems. We particularly study the reaction system ranks for a class of union-additive functions specified by minimal reaction systems introduced by Salomaa, which is closed under taking composition. More precisely, when the signature size is two, we obtain a general formula for the reaction system ranks that shows the reaction system rank of each function from this subclass depends on the characteristic of the function. Then, we study the reaction system ranks of such functions with signature size three, as well as establishing a general upper bound for reaction system ranks of such functions with one-to-one signatures for any background set.

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

Azimi S, Gratie C, Ivanov S, Petre I (2015) Dependency graphs and mass conservation in reaction systems. Theoret. Comput. Sci. 598:23–39. https://doi.org/10.1016/j.tcs.2015.02.014MathSciNetCrossRef

Azimi S, Panchal C, Czeizler E, Petre I (2015) Reaction systems models for the self-assembly of intermediate filaments. Ann. Univ. Buchar. 62(2):9–24

Azimi S, Gratie C, Ivanov S, Manzoni L, Petre I, Porreca AE (2016) Complexity of model checking for reaction systems. Theoret. Comput. Sci. 623:103–113. https://doi.org/10.1016/j.tcs.2015.11.040MathSciNetCrossRef

Bottoni P, Labella A, Rozenberg G (2019) Reaction systems with influence on environment. J. Membr. Comput. 1(1):3–19. https://doi.org/10.1007/s41965-018-00005-8MathSciNetCrossRef

Bottoni P, Labella A, Rozenberg G (2020) Networks of reaction systems. Int. J. Found. Comput. Sci. 31(01):53–71. https://doi.org/10.1142/S0129054120400043MathSciNetCrossRef

Brijder R, Ehrenfeucht A, Rozenberg G (2011) Reaction systems with duration. Computat. Cooperat. Life Lect. Notes Comput. Sci. 6610:191–202. https://doi.org/10.1007/978-3-642-20000-7_16CrossRef

Cienciala L, Ciencialová L, Csuhaj-Varjú E (2023) About reversibility in sP colonies and reaction systems. Nat. Comput. 22(1):27–39. https://doi.org/10.1007/s11047-022-09922-1MathSciNetCrossRef

Dennunzio A, Formenti E, Manzoni L, Porreca AE (2019) Complexity of the dynamics of reaction systems. Inf. Comput. 267:96–109. https://doi.org/10.1016/j.ic.2019.03.006MathSciNetCrossRef

Ehrenfeucht A, Rozenberg G (2007) Reaction systems. Fundam. Inform. 75(1–4):263–280MathSciNet

Ehrenfeucht A, Main M, Rozenberg G (2011) Functions defined by reaction systems. Int. J. Found. Comput. Sci. 22(01):167–178. https://doi.org/10.1142/S0129054111007927MathSciNetCrossRef

Ehrenfeucht A, Kleijn J, Koutny M, Rozenberg G (2012) Minimal reaction systems. In: Transactions on Computational Systems Biology XIV. Lecture Notes in Comput. Sci., vol. 7625, pp. 102–122. Springer, Berlin, Heidelberg https://doi.org/10.1007/978-3-642-35524-0_5

Ehrenfeucht A, Kleijn J, Koutny M, Rozenberg G (2017) Evolving reaction systems. Theoret. Comput. Sci. 682:79–99. https://doi.org/10.1016/j.tcs.2016.12.031MathSciNetCrossRef

Ehrenfeucht A, Petre I, Rozenberg G (2017) Reaction Systems: A Model of Computation Inspired by the Functioning of the Living Cell. In: The Role of Theory in Computer Science: Essays Dedicated to Janusz Brzozowski. pp. 1–32. World Scientific, https://doi.org/10.1142/9789813148208_0001

Genova D, Hoogeboom HJ, Jonoska N (2017) A graph isomorphism condition and equivalence of reaction systems. Theoret. Comput. Sci. 701:109–119. https://doi.org/10.1016/j.tcs.2017.05.019MathSciNetCrossRef

Genova D, Hoogeboom HJ, Prodanoff Z (2020) Extracting reaction systems from function behavior. J. Membr. Comput. 2(3):194–206. https://doi.org/10.1007/s41965-020-00045-zMathSciNetCrossRef

Holzer M, Rauch C (2023) Computational complexity of reversible reaction systems. In: Reversible Computation. Lecture Notes in Comput. Sci., vol. 13960, pp. 40–54. Springer, Cham https://doi.org/10.1007/978-3-031-38100-3_4

Intekhab H, Lim J, Teh WC (2023) Ranks of compositionally closed minimal reaction systems. Indian J Pure Appl Math. https://doi.org/10.1007/s13226-023-00411-4CrossRef

Manzoni L, Pocas D, Porreca AE (2014) Simple reaction systems and their classification. Int. J. Found. Comput. Sci. 25(04):441–457. https://doi.org/10.1142/S012905411440005XMathSciNetCrossRef

Manzoni L, Porreca AE, Rozenberg G (2020) Facilitation in reaction systems. J. Membr. Comput. 2(3):149–161. https://doi.org/10.1007/s41965-020-00044-0MathSciNetCrossRef

Salomaa A (2014) Compositions of reaction systems. J. Autom. Lang. Comb. 19(1–4):279–290MathSciNet

Salomaa A (2015) Two-step simulations of reaction systems by minimal ones. Acta Cybernet. 220, 247–257. https://doi.org/10.14232/actacyb.22.2.2015.2

Teh WC (2018) Compositions of functions and permutations specified by minimal reaction systems. Int. J. Found. Comput. Sci. 29(7):1165–1179. https://doi.org/10.1142/S0129054118500272MathSciNetCrossRef

Teh WC, Atanasiu A (2017) Irreducible reaction systems and reaction system rank. Theoret. Comput. Sci. 666:12–20. https://doi.org/10.1016/j.tcs.2016.08.021MathSciNetCrossRef

Teh WC, Atanasiu A (2017) Minimal reaction systems revisited and reaction system rank. Int. J. Found. Comput. Sci. 28(3):247–261. https://doi.org/10.1142/S0129054117500162MathSciNetCrossRef

Teh WC, Atanasiu A (2020) Simulation of reaction systems by the strictly minimal ones. J. Membr. Comput. 2(3):162–170. https://doi.org/10.1007/s41965-020-00042-2MathSciNetCrossRef

Teh WC, Lim J (2022) Evolvability of reaction systems and the invisibility theorem. Theoret. Comput. Sci. 924:17–33. https://doi.org/10.1016/j.tcs.2022.03.039MathSciNetCrossRef

Teh WC, Nguyen KT, Chen CY (2021) Ranks of strictly minimal reaction systems induced by permutations. Theoret. Comput. Sci. 872:1–14. https://doi.org/10.1016/j.tcs.2020.12.015MathSciNetCrossRef

Title: Ranks of functions specified by minimal reaction systems and induced by images of singletons
Authors: Husain Intekhab
Wen Chean Teh
Publication date: 24-02-2024
Publisher: Springer Netherlands
Published in: Natural Computing
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-024-09973-6

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