D 2019

APCol Systems with Verifier Agents

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

Základní údaje

Originální název

APCol Systems with Verifier Agents

Autoři

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

Vydání

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

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10200 1.2 Computer and information sciences

Stát vydavatele

Švýcarsko

Utajení

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

Forma vydání

tištěná verze "print"

Odkazy

URL

Označené pro přenos do RIV

Ano

Kód RIV

RIV/47813059:19240/19:A0000638

Organizační jednotka

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

ISBN

978-3-030-12796-1

DOI

https://doi.org/10.1007/978-3-030-12797-8_8

Klíčová slova anglicky

P colony; membrane systems; PCol automata

Štítky

SGS132016, ÚI

Příznaky

Mezinárodní význam, Recenzováno

Návaznosti

LQ1602, projekt VaV.
Změněno: 4. 1. 2021 11:57, Mgr. Kamil Matula, Ph.D.

Anotace

V originále

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.
Zobrazeno: 22. 11. 2026 02:59