Some Variants in Communication of Parallel Communicating Pushdown Automata
Balan, M. Sakthi, Kamala Krithivasan, Madhu Mutyam · Journal of automata, languages and combinatorics · 2003
We consider automata systems consisting of several pushdown automata working in parallel and communicating the contents of their stacks by request. We show that centralized non-returning parallel communicating pushdown automata systems with three components recognize all recursively enumerable languages. We also show that centralized returning pushdown automata systems accept non-ET0L languages. We study two variants of communication: one uses filters in communication and in the other only specified number of symbols are communicated. We prove that all these systems accept the family of recursively enumerable languages both in the centralized and in the non—centralized strategies and in both returning and non-returning communication modes with only two components.