k 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

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.

Files attached

Ciencialova-Cienciala-Varju_Further-Results-on-the-Power-of-Generating-APCol-Systems.pdf
Request the author's version of the file