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: [email protected] | Institut für Informatik, Universität Leipzig, Germany. E-mail: [email protected] | LaBRI, Université Bordeaux 1, France. E-mail: [email protected]

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