k 2019

Further Results on the Power of Generating APCol Systems

CIENCIALOVÁ, Lucie; Luděk CIENCIALA a Erzsébet CSUHAJ-VARJÚ

Základní údaje

Originální název

Further Results on the Power of Generating APCol Systems

Autoři

CIENCIALOVÁ, Lucie; Luděk CIENCIALA a Erzsébet CSUHAJ-VARJÚ

Vydání

Seventeenth Brainstorming Week on Membrane Computing, 2019

Další údaje

Jazyk

angličtina

Typ výsledku

Prezentace na konferencích

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Španělsko

Utajení

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

Odkazy

URL

Označené pro přenos do RIV

Ne

Organizační jednotka

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

Klíčová slova anglicky

P Colonies; P Systems; APCol Systems; Generating power; Membrane Computing

Štítky

SGS112019, ÚI

Příznaky

Mezinárodní význam, Recenzováno

Návaznosti

LQ1602, projekt VaV.
Změněno: 21. 2. 2022 13:45, Mgr. Kamil Matula, Ph.D.

Anotace

V originále

In this paper we continue our investigations in APCol systems (Automatonlike P colonies), variants of P colonies where the environment of the agents is given by a string and the functioning of the system resembles to the functioning of standard finite automaton. We first deal with the concept of determinism in these systems and compare deterministic APCol systems with deterministic register machines. Then we focus on generating non-deterministic APCol systems with only one agent. We show that these systems are as powerful as 0-type grammars, i.e., generate any recursively enumerable language. If the APCol system is non-erasing, then any context-sensitive language can be generated by a non-deterministic APCol systems with only one agent.
Zobrazeno: 18. 11. 2026 16:00