Ashish Choudhary,
Kamala Krithivasan,
Victor Mitrana
(2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
A parallel communicating automata system consists of several automata working independently in parallel and
communicating with each other by request with the aim of recognizing a word.
Rather surprisingly, returning parallel communicating finite automata systems are equivalent
to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata.
Some open problems are finally formulated.