2019
APCol Systems with Verifier Agents
CIENCIALOVÁ, Lucie; Erzsébet CSUHAJ-VARJÚ; György VASZIL a Luděk CIENCIALAZá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
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
Klíčová slova anglicky
P colony; membrane systems; PCol automata
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.