Some undecidable problems for parallel communicating finite automata systems

Authors
Martin-Vide, C Mitrana, V
Citation
C. Martin-vide et V. Mitrana, Some undecidable problems for parallel communicating finite automata systems, INF PROCESS, 77(5-6), 2001, pp. 239-245
Citations number
11
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
77
Issue
5-6
Year of publication
2001
Pages
239 - 245
Database
ISI
SICI code
0020-0190(20010331)77:5-6<239:SUPFPC>2.0.ZU;2-6
Abstract
We investigate the decidability status of some problems for parallel commun icating finite automata systems. We show that the universe and the emptines s problems are undecidable for cpcfa and pcfa with at least five components and rpcfa and cpcfa with at least four components, respectively. Consequen tly, the equivalence and inclusion problems are also undecidable for these automata systems. Some open problems are finally formulated. (C) 2001 Elsev ier Science B.V. All rights reserved.