D 2019

APCol Systems with Verifier Agents

CIENCIALOVÁ, Lucie; Erzsébet CSUHAJ-VARJÚ; György VASZIL and Luděk CIENCIALA

Basic information

Original name

APCol Systems with Verifier Agents

Authors

CIENCIALOVÁ, Lucie; Erzsébet CSUHAJ-VARJÚ; György VASZIL and Luděk CIENCIALA

Edition

Cham, Membrane Computing. CMC 2018. Lecture Notes in Computer Science, p. 95-107, 13 pp. 2019

Publisher

Springer

Other information

Language

English

Type of outcome

Proceedings paper

Field of Study

10200 1.2 Computer and information sciences

Country of publisher

Switzerland

Confidentiality degree

is not subject to a state or trade secret

Publication form

printed version "print"

References:

Marked to be transferred to RIV

Yes

RIV identification code

RIV/47813059:19240/19:A0000638

Organization unit

Faculty of Philosophy and Science in Opava

ISBN

978-3-030-12796-1

Keywords in English

P colony; membrane systems; PCol automata

Tags

Tags

International impact, Reviewed

Links

LQ1602, research and development project.
Changed: 4/1/2021 11:57, Mgr. Kamil Matula, Ph.D.

Abstract

In the original language

APCol systems (Automaton-like P colonies) are variants of P colonies where the environment is given by a string and the agents change their own states and the environmental string similarly to automata. By the original definition, the input (initial environmental) string is accepted if it can be reduced to the empty word. In this paper, we continue the examination of a variant of APCol systems where the agents explore and verify their common environment (the notion was introduced as verifying APCol systems). In this case, an input string of length n is accepted if there is a halting computation c such that the length of the environmental strings remains unchanged during the computation and for every agent and for each position each i, 1 < = i < =n , there is an environmental string obtained by c such that the agent applies a rule to position i. Improving a previous result, we show that APCol systems with verifier agents simulate nondeterministic two-way multihead automata. The result implies that any language in NSPACE(logn) can be accepted by an APCol system with verifier agents.

Files attached

Ciencialova2019_Chapter_APColSystemsWithVerifierAgents.pdf
Request the author's version of the file