2019
Further Results on the Power of Generating APCol Systems
CIENCIALOVÁ, Lucie; Luděk CIENCIALA and Erzsébet CSUHAJ-VARJÚBasic information
Original name
Further Results on the Power of Generating APCol Systems
Authors
CIENCIALOVÁ, Lucie; Luděk CIENCIALA and Erzsébet CSUHAJ-VARJÚ
Edition
Seventeenth Brainstorming Week on Membrane Computing, 2019
Other information
Language
English
Type of outcome
Presentations at conferences
Field of Study
10201 Computer sciences, information science, bioinformatics
Country of publisher
Spain
Confidentiality degree
is not subject to a state or trade secret
References:
Marked to be transferred to RIV
No
Organization unit
Faculty of Philosophy and Science in Opava
Keywords in English
P Colonies; P Systems; APCol Systems; Generating power; Membrane Computing
Tags
International impact, Reviewed
Links
LQ1602, research and development project.
Changed: 21/2/2022 13:45, Mgr. Kamil Matula, Ph.D.
Abstract
In the original language
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.