nach oben

Natural Computing

11.04.2024 | Research

On the spectrum between reaction systems and string rewriting

verfasst von: Artiom Alhazov, Rudolf Freund, Sergiu Ivanov

Erschienen in: Natural Computing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Reaction systems are a model of computing aiming to formalize biochemistry by capturing the qualitative relations between the species, and explicitly discarding any accounts of multiplicity. From the point of view of the formal language theory, this situates them in the realm of set rewriting. In this work, we propose a series of extensions of reaction systems to use strings. These extensions form a spectrum in the sense that all of them honor the hallmark features of the original model: the threshold principle and the non-permanency principle. We thoroughly discuss the details of the structure and the behavior of these variants, and commence studying their expressive power by comparing them to some classic models of computing.

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

Classically, regular rules have exactly one non-terminal in the left-hand side, with the right-hand side of the form \(\lambda \), a, or aB, \(a \in T\) and \(B \in V {\setminus } T\). This example includes the renaming rules \({\bar{A}} \rightarrow A\) and \({\bar{B}} \rightarrow B\). These would correspond to \(\epsilon \)-transitions in the finite automaton, which can be avoided by a simple transformation on the non-terminals of the grammar.

The first argument of \(\textsf{mctx}\) is the context and the second is the state. This function need not be commutative, nor deterministic.

In other words, k is the quotient and t the remainder of dividing \(|w|_a\) by 2.

More generally, mctx; may be the shuffle of \(\gamma '\) and w,

https://static-content.springer.com/image/art%3A10.1007%2Fs11047-024-09986-1/MediaObjects/11047_2024_9986_IEq401_HTML.gif

See also Remark 4 for a discussion of \(\textsf{post}\) taken to be \(\textsf{flat}\) in Definition 6.

Formally, the type of this function is \(\textsf{sort}_1: {{\mathcal {P}}({\mathbb {N}} \times V^*)} \rightarrow {\mathcal {P}}\big (({\mathbb {N}} \times V^*)^*\big )\).

Formally, the type of this function is \(\mathsf {cat_2}: {({\mathbb {N}} \times V^*)^*} \rightarrow V^*\). Note that \(\textsf{cat}_2\) discards the first elements of the pairs in the argument sequence, and just concatenates the words in the order in which the appear.

Often this new cell contains a special blank symbol \(\flat \in \Sigma \), designating the fact the cell does not yet contain “useful” information. In this paper, we do not rely on the distinction between \(\flat \) and \(\Sigma {\setminus } \{\flat \}\), so we do not emphasize it.

Alhazov A, Aman B, Freund R, Ivanov S (2016a) Simulating R systems by P systems. In: Leporati A, Rozenberg G, Salomaa A, Zandron C (eds) Membrane computing—17th international conference, CMC 2016, Milan, Italy, July 25–29, 2016, Revised selected papers. Lecture notes in computer science, vol 10105, pp 51–66. Springer, Berlin. https://doi.org/10.1007/978-3-319-54072-6_4

Alhazov A, Freund R, Verlan S (2016b) P systems working in maximal variants of the set derivation mode. In: Leporati A, Rozenberg G, Salomaa A, Zandron C (eds) Membrane computing—17th international conference, CMC 2016, Milan, Italy, July 25-29, 2016, Revised selected papers. Lecture notes in computer science, vol 10105, pp 83–102. Springer, Cham. https://doi.org/10.1007/978-3-319-54072-6_6

Alhazov A, Freund R, Ivanov S, Oswald M (2021) Relations between control mechanisms for sequential grammars. Fundam Informaticae 181(2–3):239–271. https://doi.org/10.3233/FI-2021-2058MathSciNetCrossRef

Alhazov A, Freund R, Ivanov S, Oswald M (2022) Variants of derivation modes for which purely catalytic P systems are computationally complete. Theor Comput Sci 920:95–112. https://doi.org/10.1016/J.TCS.2022.03.007MathSciNetCrossRef

Alhazov A, Ferrari-Dominguez V, Freund R, Glade N, Ivanov S (2023) A P systems variant for reasoning about sequential controllability of Boolean networks. Theor Comput Sci 970:114056. https://doi.org/10.1016/j.tcs.2023.114056MathSciNetCrossRef

Azimi S, Iancu B, Petre I (2014) Reaction system models for the heat shock response. Fundam Informaticae 131(3–4):299–312. https://doi.org/10.3233/FI-2014-1016MathSciNetCrossRef

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

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

Azimi S, Panchal C, Mizera A, Petre I (2017) Multi-stability, limit cycles, and period-doubling bifurcation with reaction systems. Int J Found Comput Sci 28(08):1007–1020. https://doi.org/10.1142/S0129054117500368MathSciNetCrossRef

Brijder R, Ehrenfeucht A, Main MG, Rozenberg G (2011) A tour of reaction systems. Int J Found Comput Sci 22(7):1499–1517. https://doi.org/10.1142/S0129054111008842MathSciNetCrossRef

Cocke J, Minsky M (1964) Universality of tag systems with P=2. J ACM 11(1):15–20MathSciNetCrossRef

Csuhaj-Varjú E, Vaszil G (2002) P automata or purely communicating accepting P systems. In: Paun G, Rozenberg G, Salomaa A, Zandron C (eds) Membrane computing, international workshop, WMC-CdeA 2002, Curtea de Arges, Romania, August 19–23, 2002, Revised Papers. Lecture notes in computer science, vol 2597, pp 219–233. Springer, Berlin. https://doi.org/10.1007/3-540-36490-0_14

Dassow J, Păun G (1989) Regulated rewriting in formal language theory. Springer, Heidelberg. https://www.springer.com/de/book/9783642749346

Dennunzio A, Formenti E, Manzoni L (2015a) Reaction systems and extremal combinatorics properties. Theor Comput Sci 598:138–149. https://doi.org/10.1016/J.TCS.2015.06.001

Dennunzio A, Formenti E, Manzoni L, Porreca AE (2015b) Ancestors, descendants, and gardens of Eden in reaction systems. Theor Comput Sci 608:16–26. https://doi.org/10.1016/j.tcs.2015.05.046. From Computer Science to Biology and Back

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 Informaticae 75(1–4):263–280

Freund R (2019) A general framework for sequential grammars with control mechanisms. In: Hospodár M, Jirásková G, Konstantinidis S (eds) Descriptional complexity of formal systems—21st IFIP WG 1.02 international conference, DCFS 2019, Košice, Slovakia, July 17–19, 2019, Proceedings. Lecture notes in computer science, vol 11612, pp 1–34. Springer, Cham. https://doi.org/10.1007/978-3-030-23247-4_1

Freund R, Staiger L (2019) Turing machines with activations of transitions. In: Freund R, Holzer M, Sempere JM (eds) Eleventh workshop on non-classical models of automata and applications, NCMA 2019, Valencia, Spain, July 2–3, 2019. Österreichische Computer Gesellschaft, Vienna, pp 79–91

Freund R, Verlan S (2007) A formal framework for static (tissue) P systems. In: Eleftherakis G, Kefalas P, Păun Gh, Rozenberg G, Salomaa A (eds) Membrane computing, 8th international workshop, WMC 2007, Thessaloniki, Greece, June 25–28, 2007 Revised selected and invited papers. Lecture notes in computer science, vol. 4860, pp. 271–284. Springer, Heidelberg. https://doi.org/10.1007/978-3-540-77312-2_17

Ivanov S (2015) On the power and universality of biologically-inspired models of computation. Ph.D. thesis, University of Paris-Est, France. https://tel.archives-ouvertes.fr/tel-01272318

Ivanov S, Petre I (2020) Controllability of reaction systems. J Membr Comput 2(4):290–302. https://doi.org/10.1007/S41965-020-00055-XMathSciNetCrossRef

Ivanov S, Verlan S (2015) Random context and semi-conditional insertion-deletion systems. Fundam Informaticae 138(1–2):127–144. https://doi.org/10.3233/FI-2015-1203MathSciNetCrossRef

Ivanov S, Verlan S (2021) Single semi-contextual insertion-deletion systems. Nat Comput 20(4):703–712. https://doi.org/10.1007/S11047-021-09861-3MathSciNetCrossRef

Korec I (1996) Small universal register machines. Theor Comput Sci 168(2):267–301. https://doi.org/10.1016/S0304-3975(96)00080-1MathSciNetCrossRef

Lindenmayer A (1968) Mathematical models for cellular interaction in development. J Theor Biol 18:280–315CrossRef

Margenstern M, Rogozhin Yu (2001) About time-varying distributed H systems. In: Condon A, Rozenberg G (eds) DNA computing. Springer, Berlin, pp 53–62CrossRef

Mȩski A, Penczek W, Rozenberg G (2015) Model checking temporal properties of reaction systems. Inf Sci 313:22–42. https://doi.org/10.1016/j.ins.2015.03.048CrossRef

Mȩski A, Koutny M, Penczek W (2017) Verification of linear-time temporal properties for reaction systems with discrete concentrations. Fund Inform 154:289–306. https://doi.org/10.3233/FI-2017-1567MathSciNetCrossRef

Mȩski A, Koutny M, Penczek W (2019) Model checking for temporal-epistemic properties of distributed reaction systems. Technical report, School of Computing, University of Newcastle upon Tyne

Okubo F, Kobayashi S, Yokomori T (2012a) On the properties of language classes defined by bounded reaction automata. Theor Comput Sci 454:206–221. https://doi.org/10.1016/J.TCS.2012.03.024

Okubo F, Kobayashi S, Yokomori T (2012b) Reaction automata. Theor Comput Sci 429:247–257. https://doi.org/10.1016/j.tcs.2011.12.045. Magic in Science

Păun Gh, Rozenberg G, Salomaa A (eds) (2010) The Oxford handbook of membrane computing. Oxford University Press, Oxford

Rozenberg G, Salomaa A (eds) (1997) Handbook of formal languages, vol 1–3. Springer, Berlin. https://doi.org/10.1007/978-3-642-59136-5

Salomaa A (2014) Minimal reaction systems defining subset functions. In: Calude CS, Freivalds R, Iwama K (eds) Computing with new resources—essays dedicated to Jozef Gruska on the Occasion of His 80th Birthday. Lecture Notes in Computer Science, vol 8808, pp 436–446. Springer, Cham. https://doi.org/10.1007/978-3-319-13350-8_32

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

Verlan S (2010) Study of language-theoretic computational paradigms inspired by biology, Paris. Habilation thesis

Wikipedia contributors (2023) L-system—Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/w/index.php?title=L-system &oldid=1182891458. Online; Accessed 19-November-2023

Yokomori T, Okubo F (2021) Theory of reaction automata: a survey. J Membr Comput 3(1):63–85. https://doi.org/10.1007/S41965-021-00070-6MathSciNetCrossRef

Titel: On the spectrum between reaction systems and string rewriting
verfasst von: Artiom Alhazov
Rudolf Freund
Sergiu Ivanov
Publikationsdatum: 11.04.2024
Verlag: Springer Netherlands
Erschienen in: Natural Computing
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-024-09986-1

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