Some undecidable problems for parallel communicating finite automata systems

摘要

We investigate the decidability status of some problems for parallel communicating finite automata systems. We show that the universe and the emptiness problems are undecidable for cpcfa and pacfa with at least five components and recfa and cpcfa with at least four component, respectively. Consequently, the equivalence and inclusion problems are also undecidable for these automata systems. Some open problems are finally formulated.