Conţinutul numărului revistei |
Articolul precedent |
Articolul urmator |
522 0 |
SM ISO690:2012 ALHAZOV, Artiom, FREUND, Rudolf, IVANOV, Sergiu. P systems with randomized right-hand sides of rules. In: Theoretical Computer Science, 2020, nr. 805, pp. 144-160. ISSN 0304-3975. DOI: https://doi.org/10.1016/j.tcs.2018.07.016 |
EXPORT metadate: Google Scholar Crossref CERIF DataCite Dublin Core |
Theoretical Computer Science | |||||||
Numărul 805 / 2020 / ISSN 0304-3975 /ISSNe 1879-2294 | |||||||
|
|||||||
DOI:https://doi.org/10.1016/j.tcs.2018.07.016 | |||||||
Pag. 144-160 | |||||||
|
|||||||
Rezumat | |||||||
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. |
|||||||
Cuvinte-cheie P system, Randomized rules, Tissue P system |
|||||||
|