Parallel Communicating Finite Automata: The Non-Forgetting Model
Electronic Proceedings in Theoretical Computer Science · 25.06.2026 · 446 · 89-103
DOI: 10.4204/eptcs.446.6 ↗Kurz gefasst
Fachartikel in der Zeitschrift Electronic Proceedings in Theoretical Computer Science, online erschienen am 25.06.2026. Verfasst von Jana Schulz. Die Arbeit nennt 12 Literaturangaben.
Abstract (Originalsprache)
Parallel Communicating Finite Automata (PCFA) are systems of several finite automata that can communicate by requesting the state of another automaton. As an attempt to make PCFA as defined in [8] and [2] more realistic, the non-forgetting model is introduced where automata retain their own states while querying. As in previous publications, several variants of these automata systems are considered. The computational capacity of the non-forgetting model is investigated and compared to''forgetting''systems and multi-head finite automata. It is shown that most variants of non-forgetting PCFA are as powerful as multi-head automata in the deterministic and nondeterministic cases where the number of automata equals the number of heads. The only exception is the special case of deterministic centralized systems in non-returning mode. Here, a strict inclusion is proved. In the course of this proving, a proof from [2] is completed. With that, this paper answers some questions for nfPCFA that are open for the classical''forgetting''case.
Zitieren
APA
Schulz, J. (2026). Parallel Communicating Finite Automata: The Non-Forgetting Model. Electronic Proceedings in Theoretical Computer Science, 446, 89-103. https://doi.org/10.4204/eptcs.446.6
Vancouver
Schulz J. Parallel Communicating Finite Automata: The Non-Forgetting Model. Electronic Proceedings in Theoretical Computer Science. 2026;446:89-103. doi:10.4204/eptcs.446.6
BibTeX
@article{Schulz2026,
author = {Schulz, Jana},
title = {Parallel Communicating Finite Automata: The Non-Forgetting Model},
journal = {Electronic Proceedings in Theoretical Computer Science},
year = {2026},
volume = {446},
pages = {89--103},
doi = {10.4204/eptcs.446.6}
}
EUVIMED