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

SOSÍK, Petr

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

Plný text u vydavatele

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ě

DOI

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

UT WoS

000826835000001

EID Scopus

2-s2.0-85134545344

Klíčová slova anglicky

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

Štítky

2022, RIV2023, SGS82022, ÚI

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.
Zobrazeno: 18. 11. 2026 16:09