Automata for interaction protocols in multiagent systems

Interaction among agents in multiagent systems may be tackled in various ways. The most common one though relies on the notion of a protocol the agents follow in order to structure the messages they exchange. In the literature however, one notices that the interpretation and representation of interaction protocols vary. We set a formal framework based on the theory of computing languages. After a quick introduction to some basic definitions of this theory applied to the domain of interaction protocols we develop the concepts of deterministic and nondeterministic protocols. We show that these two protocol classes are identical. Actually, although this property of nondeterminism introduces some true flexibility for protocol design it does not allow for an extension of this class. Then we focus on the definition of syntactically correct protocols and present grammars for generating authorized message sequences. We also show that the class of interaction protocols used in multiagent systems is the class of regular protocols. Finally we conclude with some limits and weaknesses of this class