2022
Morphogenetic computing: computability and complexity results
SOSÍK, PetrBasic information
Original name
Morphogenetic computing: computability and complexity results
Authors
Edition
Natural Computing, Springer Science and Business Media, 2022, 1567-7818
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Germany
Confidentiality degree
is not subject to a state or trade secret
References:
Impact factor
Impact factor: 2.100
Marked to be transferred to RIV
Yes
RIV identification code
RIV/47813059:19240/22:A0001000
Organization unit
Faculty of Philosophy and Science in Opava
UT WoS
EID Scopus
Keywords in English
Membrane computing; Morphogenetic system; P versus NP; Self-assembly; Universal computation
Tags
International impact, Reviewed
Changed: 20/10/2023 15:32, Mgr. Kamil Matula, Ph.D.
Abstract
In the original language
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.