2022
Morphogenetic computing: computability and complexity results
SOSÍK, PetrZákladní údaje
Originální název
Morphogenetic computing: computability and complexity results
Autoři
Vydání
Natural Computing, Springer Science and Business Media, 2022, 1567-7818
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Německo
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Impakt faktor
Impact factor: 2.100
Označené pro přenos do RIV
Ano
Kód RIV
RIV/47813059:19240/22:A0001000
Organizační jednotka
Filozoficko-přírodovědecká fakulta v Opavě
UT WoS
EID Scopus
Klíčová slova anglicky
Membrane computing; Morphogenetic system; P versus NP; Self-assembly; Universal computation
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 20. 10. 2023 15:32, Mgr. Kamil Matula, Ph.D.
Anotace
V originále
A morphogenetic (M) system is an abstract computational model combining properties of membrane (P) systems, such as computing via abstract particles in separate compartments regulating their workflow, with algorithmic self-assembly generalizing original Wang tiles to arbitrary polytopes forming complex shapes in 2D/3D (or generally, dD) space. Even very simple morphogenetic systems can exhibit complex self-organizing behaviour and, at the abstract level, one can observe characteristic properties of morphogenetic phenomena such as controlled growth, self-reproduction, homeostasis and self-healing. Here we focus on computational aspects of the morphogenetic systems. After summarizing a series of results related to their computational universality (in the Turing sense) and computational complexity, we present two small universal M systems (one of them self-healing) and we also demonstrate how morphogenetic systems relate to the classes P and NP.