J 2022

Morphogenetic computing: computability and complexity results

SOSÍK, Petr

Basic information

Original name

Morphogenetic computing: computability and complexity results

Authors

SOSÍK, Petr

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:

Plný text u vydavatele

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

DOI

https://doi.org/10.1007/s11047-022-09899-x

UT WoS

000826835000001

EID Scopus

2-s2.0-85134545344

Keywords in English

Membrane computing; Morphogenetic system; P versus NP; Self-assembly; Universal computation

Tags

2022, RIV2023, SGS82022, ÚI

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.
Displayed: 18/11/2026 16:00