Skip to Main content Skip to Navigation
Journal articles

P systems with randomized right-hand sides of rules

Abstract : P systems are a model of distributed and compartmentalized multiset rewriting, complete with various signal transmission mechanisms. We introduce a novel kind of P systems in which rules are dynamically constructed in each step by non-deterministic pairing of left-hand and right-hand sides. We define three variants of right-hand side randomization and compare each of them with the power of conventional P systems. It turns out that all three variants enable non-cooperative P systems to generate exponential (and thus non-semi-linear) number languages. We also give a binary normal form for one of the variants of P systems with randomized rule right-hand sides. Finally, we also discuss extensions of the three variants to tissue P systems, i.e., P systems on an arbitrary graph structure.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01879398
Contributor : Frédéric Davesne <>
Submitted on : Tuesday, July 21, 2020 - 5:16:08 PM
Last modification on : Tuesday, July 21, 2020 - 5:32:41 PM

File

TCS_2020_AA_RF_SI_hal.pdf
Files produced by the author(s)

Identifiers

Citation

Artiom Alhazov, Rudolf Freund, Sergiu Ivanov. P systems with randomized right-hand sides of rules. Theoretical Computer Science, Elsevier, 2020, 805, pp.144--160. ⟨10.1016/j.tcs.2018.07.016⟩. ⟨hal-01879398⟩

Share

Metrics

Record views

103

Files downloads

40