On Communicating Automata with Bounded Channels

Issue title: Half a Century of Inspirational Research: Honoring the Scientific Influence of Antoni Mazurkiewicz

Article type: Research Article

Authors: Genest, Blaise | Kuske, Dietrich | Muscholl, Anca

Affiliations: IRISA/CNRS, Campus de Beaulieu, Rennes, France. E-mail: Blaise.Genest@liafa.jussieu.fr | Institut für Informatik, Universität Leipzig, Germany. E-mail: kuske@informatik.uni-leipzig.de | LaBRI, Université Bordeaux 1, France. E-mail: anca@labri.fr

Abstract: We review the characterization of communicating finite-state machines whose behaviors have universally or existentially bounded channels. These results rely on the theory of Mazurkiewicz traces. We investigate the question whether channel bound conditions are decidable for a given communicating finite-state machine.

Keywords: Communicating automata, Mazurkiewicz traces

Journal: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 147-167, 2007