J 2022

Morphogenetic computing: computability and complexity results

SOSÍK, Petr

Zá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í

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ě

EID Scopus

Klíčová slova anglicky

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

Štítky

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.

Přiložené soubory

Sosik_Morphogenetic-computing-computability-and-complexity-results.pdf
Požádat o autorskou verzi souboru