J 2016

Small (purely) catalytic P systems simulating register machines

SOSÍK, Petr a Miroslav LANGER

Základní údaje

Originální název

Small (purely) catalytic P systems simulating register machines

Autoři

SOSÍK, Petr a Miroslav LANGER

Vydání

Theoretical Computer Science, Amsterdam, Elsevier, 2016, 0304-3975

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Nizozemské království

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.698

Označené pro přenos do RIV

Ne

Organizační jednotka

Filozoficko-přírodovědecká fakulta v Opavě

Klíčová slova anglicky

Membrane computing; Catalytic P system; Universal computation; Register machine

Štítky

Příznaky

Mezinárodní význam, Recenzováno

Návaznosti

ED1.1.00/02.0070, projekt VaV.
Změněno: 19. 3. 2020 14:20, doc. Ing. Petr Sosík, Dr.

Anotace

V originále

The paper contributes to the topic of (purely) catalytic P systems. Catalytic P systems represent the original and likely the simplest class of membrane computing models. It is known that (purely) catalytic P systems with two (respectively three) catalysts and one membrane can simulate any Minsky register machine and, hence, they are computationally complete. However, the problem of minimal size of such a universal catalytic P system remains open for about ten years. We improve known results about small catalytic P systems simulating register machines in three different modes (generating, accepting, computing functions). Together with some specific universal register machine [7], one could eventually construct a small universal catalytic P system. As a consequence, we also improve the previous construction of a minimal catalytic P system generating a non-semilinear set, diminishing the number of necessary rules from 29 to 24. (C) 2015 Elsevier B.V. All rights reserved.

Přiložené soubory

Cat_Non_Semilin_NCMA_TCS.pdf
Požádat o autorskou verzi souboru