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
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
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.