M Mukund, K Narayan Kumar, J Radhakrishnan and M Sohoni
Report TCS-97-4, SPIC Mathematical Institute, Madras, India (1997)
This paper is a step towards developing a new automata-theoretic framework for describing distributed finite-state systems with asynchronous communication. If we assume that messages can be delayed arbitrarily in transit, it is reasonable to model the global behaviour of such systems in terms of finite-state automata equipped with blind counters---that is, counters which cannot be tested for zero.
We analyse the languages accepted by such automata and show that it is decidable whether the language of such an automaton is empty. We also develop a variety of pumping lemmas which can be used to show that certain languages are not accepted by these automata.
Our main result is that the subclass of languages accepted by these automata which is closed under complementation is precisely the class of regular languages. In the context of asynchronous protocols, our result implies that robust finite-state protocols use bounded buffers. In other words, messages are used only for hand-shaking---that is, for coordinating the interaction between different processes and the environment.
It is well known that automata with blind counters are closely related to Petri nets. However, our definition of languages is more appropriate for reasoning about asynchronous communication and is different from the definition used in the theory of Petri nets.